취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2698번 문제인 인접한 비트의 개수이다.
문제는 아래 링크를 확인하자.

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

양의 정수 n과 n보다 작은 음이 아닌 정수 k에 대하여 dp[n][k][bit]를 길이가 n이면서 인접한 1의 쌍이 k개 있는, 마지막 수가 bit인 수열 S의 개수로 정의하자. 이 때 각 dp[n][k][bit]을 dp[n-1][k][bit]와 dp[n-1][k-1][bit]을 이용해 어떻게 나타낼 수 있는지를 고민해 점화식을 세워 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int dp[101][101][2]; // [n][k]

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	dp[0][0][0] = 1;
	for (int n = 1; n < 101; n++) {
		dp[n][0][0] = dp[n - 1][0][0] + dp[n - 1][0][1];
		dp[n][0][1] = dp[n - 1][0][0];
		for (int k = 1; 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] + dp[n - 1][k - 1][1];
		}
	}

	int T; cin >> T;
	while (T--) {
		int n, k; cin >> n >> k;
		cout << dp[n][k][0] + dp[n][k][1] << '\n';
	}
}