[BOJ] 백준 2698번 : 인접한 비트의 개수 (JAVA)

문제

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

 

 

입력

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

 

 

출력

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

 

 

풀이

다이나믹 프로그래밍을 이용하여 풀 수 있는 문제였습니다.

 

이 문제에서의 핵심은 특정 비트 뒤에 어떤 비트가 붙느냐에 따라 인접한 비트의 개수가 달라진다는 사실을 캐치하는 것이었습니다.

 

여기서 특정 비트는 0 또는 1이고, 이 뒤에 0 또는 1이 어떻게 붙느냐에 따라 인접한 비트의 개수가 1개 증가하거나, 그대로 유지됩니다.

 

예시를 봅시다.

 

 

<맨 뒤 비트가 0>

010 + 0 => 0100

010 + 1 => 0101

 

 

<맨 뒤 비트가 1>

011 + 0 => 0110

011 + 1 => 0111

 

 

위의 예시를 보면 알 수 있듯이, 맨 뒤 비트가 0이면 항상 인접한 비트의 개수가 증가하지 않습니다.

따라서, dp[n][k][0] = dp[n - 1][k][0] + dp[n - 1][k][1] 라는 식을 도출해 낼 수 있습니다.

여기서 n은 비트의 길이이며, k는 인접한 비트의 개수를 의미하고, [n][k][0] 에서 [0]은 맨 뒤 비트가 0임을 의미합니다.

 

맨 뒤 비트가 1이면, 뒤에 첨가되는 비트가 0이면 인접한 비트의 개수가 그대로지만, 첨가되는 비트가 1이면 인접한 비트의 개수가 1이 증가하게 됩니다.

 

위의 내용을 토대로, dp[n][k][1] = A + dp[n - 1][k][0] 라는 식을 도출해 낼 수 있습니다.

일단, 첨가되는 비트가 0이면 무조건 인접한 비트의 개수가 증가하지 않으므로 그대로 더해주면 됩니다.

다만, 첨가되는 비트가 1이면 식이 조금 달라졌습니다. 이 부분을 설명하기 위해서 일단 여기에 해당하는 수식은 A로 설정해 두었습니다.

 

A는 n = 1, 2, 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][1]

110 -> dp[3][1][0]

111 -> dp[3][2][1]

 

 

위 예시를 볼 때, dp[3][1][1] = 1 입니다.

또, dp[2][0][1] = 1 이며, dp[2][1][0] = 0 입니다.

그리고 dp[3][1][1] = dp[2][0][1] + dp[2][1][0] = 1 + 0 = 1 과 동일합니다.

 

dp[3][2][1] = 1 입니다.

또, dp[2][1][1] = 1 이며, dp[2][2][0] = 0 입니다.

그리고 dp[3][2][1] = dp[2][1][1] + dp[2][2][0] = 1 + 0 = 1 과 동일합니다.

 

여기서, dp[n][k][1] = dp[n - 1][k - 1][1] + dp[n - 1][k][0] 라는 식을 최종적으로 도출해 낼 수 있습니다.

 

정리하면, 아래와 같은 점화식을 사용하여 dp 배열을 n = 100, k = 100까지 쭉 저장해 둔 뒤, 입력값에 맞춰서 출력하면 됩니다.

 

 

<최종 점화식>

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]

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.