[백준] 2698-인접한 비트의 개수(C++)

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

2698번: 인접한 비트의 개수

 

전형적인 dp문제입니다.

 

결과를 도출할때 2가지로 나누어 생각했습니다.

 

• 끝이 0일때,
• 끝이 1일때

만약 n=4, k=1일때, 경우의수는 

1100

0110

0011

1101

1011

이렇게 5가지 입니다.

 

즉, 

i는 n, j는 k 값일때

 

각각

dp[idp[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]

 

 

아래는 정답코드입니다.

#include <iostream>
using namespace std;
int t,n, k;
int dp[101][101][2] = { 0, };
int main() {

	cin >> t;
	
	dp[1][0][0] = 1; //n k 마지막수가 0인지 1인지
	dp[1][0][1] = 1;

	for (int i = 2; i <=100; 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];
		}
	}
	while (t--) {
		cin >> n >> k;
		cout << dp[n][k][0] + dp[n][k][1] << "\n";

	}
	
}