BOJ#2698 인접한 비트의 개수

BOJ#2698 인접한 비트의 개수

* 문제

https://www.acmicpc.net/problem/2698

* 풀이

문제가 어려울 때는 동적계획법의 정의에 대해 다시 생각해봅시다.

1. 복잡한 문제를 간단한 여러 문제로 나누어 푸는 방법

   (하위 문제들의 답을 저장한다, 메모이제이션)

2. dp정의와 점화식을 도출해보자

,

1. 복잡한 문제를 간단한 여러 문제로 나누어 푸는 방법

일단 복잡한 문제란 길이가 긴 수열이라는 뜻이고 (우리가 손으로 풀 수 없음)

간단한 하위 문제란 길이가 짧은 수열이라는 것입니다. (우리가 손으로 충분히 풀 수 있음)

결국 짧은 길이의 수열에서 점점 길이를 증가시키면서 우리가 원하는 답을 구하면 되는 것입니다.

이 문제의 경우

수열의 각 자리는 0 또는 1이므로 이를 힌트로 하여 문제를 풀어보았습니다.

2. dp정의와 점화식을 도출해보자

수열의 각 자리는 0 또는 1입니다. 이를 이용하면

1) 마지막 비트가 0인 경우

   a) 이전 비트가 0인 경우 : 인접한 비트 수 변화 없음 

   b) 이전 비트가 1인 경우 : 인접한 비트 수 변화 없음

2) 마지막 비트가 1인 경우

   a) 이전 비트가 0인 경우 : 인접한 비트 수 변화 없음

   b) 이전 비트가 1인 경우 : 인접한 비트 수 변화 있음

* dp 정의

dp[n][k][m] : 길이가 n이고 인접한 비트 수가 k이고 마지막 비트가 m인 경우의 수

* dp 점화식

dp[n][k][0] = dp[n-1][k][0] + dp[n-1][k][1] 

dp[n][k][1] = dp[n-1][k][0] + dp[n-1][k-1][1]

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/master/BOJ%232698/src/Main.java

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

public class Main {

    // dp[n][k][m] : 길이가 n이고 인접한 비트 수가 k이고 마지막 비트가 m인 경우의 수
    // dp[n][k][0] = dp[n-1][k][0] + dp[n-1][k][1]
    // dp[n][k][1] = dp[n-1][k][0] + dp[n-1][k-1][1]
    static int[][][] dp = new int[101][100][2];

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        dp[1][0][0] = 1;
        dp[1][0][1] = 1;

        for (int n = 2; n <= 100; n++) {
            for (int k = 0; k < n; k++) {

                dp[n][k][0] = dp[n - 1][k][0] + dp[n - 1][k][1];
                dp[n][k][1] = dp[n - 1][k][0] + ((k > 0) ? dp[n - 1][k - 1][1] : 0);
            }
        }

        while (T-- > 0) {

            StringTokenizer st = new StringTokenizer(br.readLine());

            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());

            bw.write(dp[N][K][0] + dp[N][K][1] + "\n");

        } // ~test case loop

        bw.flush();
        bw.close();
        br.close();
    }
}