BOJ_2698_인접한 비트의 수 (Java)

[Gold IV] 인접한 비트의 개수 - 2698

문제 링크

성능 요약

메모리: 16600 KB, 시간: 116 ms

분류

다이나믹 프로그래밍

제출 일자

2025년 1월 10일 16:59:47

문제 설명

0과 1로 이루어진 수열 S가 있다. S의 첫 수는 s1이고, 마지막 수는 sn이다. S의 인접한 비트의 개수는 다음과 같이 구할 수 있다.

s₁*s₂ + s₂*s₃ + s₃*s₄ + ... + s_n-1 * s_n

위의 식을 이용하면 수열 S에서 인접한 1의 개수를 구할 수 있다. 예를들어, 011101101의 인접한 비트의 개수는 3이 되고, 111101101은 4, 010101010은 0이 된다.

수열 S의 크기 n과 k가 주어졌을 때, 인접한 비트의 개수가 k인 수열 S의 개수를 구하는 프로그램을 작성하시오.

예를 들어, n이 5이고, k가 2이면, 수열 S가 될 수 있는 수열은 다음과 같이 6가지가 있다.

11100, 01110, 00111, 10111, 11101, 11011

입력

첫째 줄에 테스트 케이스의 수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 수 2개가 공백으로 구분되어 이루어져 있다. 첫 번째 수는 n이고, 두 번째 수는 k이다. n과 k는 100을 넘지 않는 자연수이다.

출력

각 테스트 케이스에 대해 인접한 비트의 개수가 k인 수열 S의 개수를 한 줄에 하나씩 출력한다. 이 값은 2,147,483,647보다 작거나 같다.

문제 풀이

코드

package BOJ_2698_인접한비트의개수;

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static int TC, N, K, dp[][][];

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
//        br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_2698_인접한비트의개수/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        TC = Integer.parseInt(br.readLine());
        dp = new int[101][101][2];
        dp[1][0][0] = 1;
        dp[1][0][1] = 1;

        for (int i = 2; i <= 100; i++) {
            for (int j = 0; j <= i - 1; j++) {
                for (int k = 0; k < 2; k++) {
                    dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1];

                    if (j == 0) { // 이거 없으면 -1 인덱스 접근가능 오류
                        dp[i][j][1] = dp[i - 1][j][0];
                    } else {
                        dp[i][j][1] = dp[i - 1][j][0] + dp[i - 1][j - 1][1];
                    }
                }
            }
        }
        while (TC-- > 0) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            sb.append(dp[N][K][0] + dp[N][K][1]).append('\n');
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

---

더 효율적인 코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static int TC, N, K, dp[][];

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_2698_인접한비트의개수/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        TC = Integer.parseInt(br.readLine());
        dp = new int[101][101];
        dp[0][0] = 1;
        dp[1][0] = 2;
        for(int i=2;i<=100;i++){
            for(int j=i-1;j>0;j--){
                dp[i][j] = dp[i-1][j] + dp[i-2][j] + (dp[i-1][j-1] - dp[i-2][j-1]);
            }
            dp[i][0] = dp[i-1][0] + dp[i-2][0];
        }
        
        while(TC-->0){
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            sb.append(String.valueOf(dp[N][K])).append('\n');
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}