백준 2698번 인접한 비트의 개수 :: 마이구미

이 글은 백준 알고리즘 문제 2698번 "인접한 비트의 개수" 를 풀이한다.

풀이 방법으로는 동적계획법을 이용한다.

문제 링크 - https://www.acmicpc.net/problem/2698

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

s1*s2 + s2*s3 + s3*s4 + ... + sn-1 * sn

위의 식을 이용하면 수열 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

인접한 1의 개수는 위와 같은 식으로 구할 수 있다.

식을 통해 점화식의 힌트를 얻을 수 있다.

맨 뒤의 수가 1이면 뒤에 다시 1을 붙였을 때, 인접 비트의 개수는 1 더해진다.

0이라면 0 또는 1을 붙여도 인접 비트의 개수는 변화가 없다는 것을 알 수 있다.

말하고자하는 의미의 예는 다음과 같다.

01 => 011 // 0개 => 1개
00 => 000 // 0개 => 0개
00 => 001 // 0개 => 0개

위와 같은 경우를 바탕으로 만들 수 있는 점화식은 다음과 같다.

인접 비트 개수가 k개이고, n번째 수가 0일 때 수열의 개수
dp[n][k][0] = dp[n - 1][k][0] + dp[n - 1][k][1];
dp[n][k][1] = dp[n - 1][k - 1][1] + dp[n - 1][k][0];

k - 1 조건 때문에 살짝 까다로울 수 있다.

n이 1 ~ 3 까지를 확인해보면 느낌이 올 것이다.

n = 1

0 => dp[1][0][0]
1 => dp[1][0][1]

n = 2

00 => dp[2][0][0]
01 => dp[2][0][1]
10 => dp[2][0][0]
11 => dp[2][1][1]

n = 3

000 => dp[3][0][0]
001 => dp[3][0][1]
010 => dp[3][0][0]
011 => dp[3][1][1]
100 => dp[3][0][0]
101 => dp[3][0][0]
110 => dp[3][1][0]
111 => dp[3][2][1]

길이가 n일 때, 최대 k의 수는 n - 1이다.

그렇기에 각 길이(2 ~ n)를 0 ~ k 까지 수열의 개수를 누적시키면서 결과를 얻을 수 있다.

관련 문제 - 동적계획법 카테고리

Github - https://github.com/hotehrud/acmicpc/tree/master/dp

private void solve() {
    int t = sc.nextInt();
    int[][][] dp = new int[101][100][2];
    StringBuilder sb = new StringBuilder();
 
    // 인접한 비트 개수가 k개면서 n번째 비트가 0 또는 1 일때
    // dp[n][k][0] = dp[n - 1][k][0] + dp[n - 1][k][1]
    // dp[n][k][1] = dp[n - 1][k - 1][1] + dp[n - 1][k][0]
 
    dp[1][0][1] = 1; // 1
    dp[1][0][0] = 1; // 0
 
    for (int k = 0; k < 100; k++) {
 
        for (int n = 2; n <= 100; n++) {
            if (k == 0) {
                dp[n][k][1] += dp[n - 1][k][0];
            } else {
                dp[n][k][1] += dp[n - 1][k][0] + dp[n - 1][k - 1][1];
            }
            dp[n][k][0] += dp[n - 1][k][0] + dp[n - 1][k][1];
        }
 
    }
 
    while (t-- > 0) {
        int n = sc.nextInt();
        int k = sc.nextInt();
 
        sb.append((dp[n][k][0] + dp[n][k][1]) + "\n");
    }
    System.out.println(sb.toString());
}