[백준 알고리즘] 2698번 : 인접한 비트의 개수

문제

2698번 : 인접한 비트의 개수

2698번: 인접한 비트의 개수

내가 작성한 코드 (C++ 성공)

#include <iostream>

using namespace std;

int dp[101][101][2];

int main(){
	cin.tie(0);	
	int T, n, k;
	cin >> T;
	
	dp[1][0][0] = 1; // n = 1, k = 0, bit = 0;
	dp[1][0][1] = 1; // n = 1, k = 0, bit = 1;	
	
	for(int i=2; i<101; i++){
		for(int j=0; j<i; j++){
			dp[i][j][0] = dp[i-1][j][0] + dp[i-1][j][1];
			dp[i][j][1] = dp[i-1][j][0] + dp[i-1][j-1][1];
		}
	}
	
	for(int i=0; i<T; i++){
		cin >> n >> k;
		
		cout << dp[n][k][0] + dp[n][k][1] << "\n";
	}
	
	return 0;
}

 

정리

3차 배열을 이용한 동적계획법에 대한 문제였다.
수열의 크기 n 과 인접한 비트의 개수인 k 그리고 '비트'로 나타냈기 때문에 0 또는 1 해서 2가지 경우
이렇게 3가지를 통해서 3차 배열을 만들 수 있었다.

int dp[n][k][2]

점화식을 세우기 전에 이 문제의 핵심은 비트로 나타낸다는 점이다.
비트기 때문에 수열의 크기가 증가할 때마다 마지막 숫자가 0 또는 1이 붙는다.

따라서 경우의 수를 따져보면,
1) ######0 + 0 > 갯수 증가 안함
2) ######0 + 1 > 갯수 증가 안함
3) ######1 + 0 > 갯수 증가 안함
4) ######1 + 1 > 갯수 증가

마지막 숫자가 0 ( dp[n][k][0] ) 이 된다면
1, 2) 이전의 숫자가 0 (dp[n-1][k][0]) 이나 1 (dp[n-1][k][1]) 이었어도 인접한 비트의 갯수가 증가하지 않을 것이다.
따라서 인접한 비트의 갯수가 증가하지 않고 이전의 갯수와 같기 때문에
dp[n][k][0] = dp[n-1][k][0] + dp[n-1][k][1] 이 된다.
예를 들어, dp[3][1][0] (110) = dp[2][1][0] (-) + dp[2][1][1] (11) 이 된다.

마지막 숫자가 1 ( dp[n][k][1] ) 이 된다면
3) 이전의 숫자가 0 (dp[n-1][k][0]) 이면 인접한 비트의 갯수가 증가하지 않을 것이고
4) 이전의 숫자가 1 (dp[n-1][k][1]) 이면 인접한 비트의 갯수가 증가할 것이다.
따라서 이전의 숫자가 0 일 때는 인접한 비트의 갯수가 이전의 갯수와 같고
이전의 숫자가 1 일 때는 인접한 비트의 갯수(k)가 1 이 증가하기 때문에 k-1 일 경우에서 1을 더해주어야 한다.
dp[n][k][1] = dp[n-1][k][0] + dp[n-1][k-1][1] 이 된다.
이 때, 인접한 비트의 갯수가 0이라면 이전에도 인접한 비트의 갯수가 없었기 때문에
dp[n][k][1] = dp[n-1][k][0] 이 되어야 한다.
예를 들어,
dp[3][1][1] (011) = dp[2][1][0] (-) + dp[2][0][1] (01) 이 된다.
dp[3][0][1] (001) = dp[2][0][0] (00) 이 된다.

그리고 경우의 수를 직접 구해보았다.

n = 1 일 때,
0 : dp[1][0][0]
1 : dp[1][0][1]

n = 2 일 때,
00 : dp[2][0][0] += dp[1][0][0]
01 : dp[2][0][1] += dp[1][0][0]
10 : dp[2][0][0] += dp[1][0][1]
11 : dp[2][1][1] += dp[1][0][1]

dp[2][0][0] = dp[1][0][0] + dp[1][0][1] (dp[n][k][0] = dp[n-1][k][0] + dp[n-1][k][1])
dp[2][0][1] = dp[1][0][0]                    (k=0, dp[n][k][1] = dp[n-1][k][0])
dp[2][1][1] = dp[1][0][1]                    (dp[n][k][1] = dp[n-1][k-1][1])

n=3 일 때,
000 : dp[3][0][0] += dp[2][0][0]
001 : dp[3][0][1] += dp[2][0][0]
010 : dp[3][0][0] += dp[2][0][1]
011 : dp[3][1][1] += dp[2][0][1]
100 : dp[3][0][0] += dp[2][0][0]
101 : dp[3][0][1] += dp[2][0][0]
110 : dp[3][1][0] += dp[2][1][1]
111 : dp[3][2][1] += dp[2][1][1]

dp[3][0][0] = dp[2][0][0] + dp[2][0][1] (dp[n][k][0] = dp[n-1][k][0] + dp[n-1][k][1])
dp[3][0][1] = dp[2][0][0]                    (k=0, dp[n][k][1] = dp[n-1][k][0])
dp[3][1][0] = dp[2][1][1]                    (dp[n][k][0] = dp[n-1][k][1])
dp[3][1][1] = dp[2][0][1]                    (dp[n][k][1] = dp[n-1][k-1][1])
dp[3][2][0] = X                                 (0이 오게되면 인접한 갯수가 최대 1이다.)
dp[3][2][1] = dp[2][1][1]                    (dp[n][k][1] = dp[n-1][k-1][1])

 

이 문제를 풀고 풀이는 정리해보면서 솔직하게 이 문제를 다 이해했다고 생각하지 않는다.
이해가 되지 않아 여러 사람의 풀이를 보았는데 사실 이해가 잘 안된다.
어떤 부분에서 잘못 이해를 하고 있는지 어떻게 이해해야하는지에 대해서는 공부를 더 하고 더 많은 문제를 풀고나서
이 문제를 다시 풀면 그때는 지금보다 이해가 잘 될 수도 있겠지.
그래도 다른 사람의 풀이를 보면서 어느 정도 이해하는 데에도 오랜 시간이 걸렸고
문제를 풀긴 풀었지만 다른 사람의 도움을 받아 푼거나 다름이 없다.
아직 동적계획법에 대한 문제를 풀기에 실력이 부족하다고 생각한다.
하지만 다음에 비슷한 문제가 나온다면 비슷한 접근으로 풀어볼 수 있을 것 같다.