[백준 BOJ][C++]2193번 이친수 풀이: DP

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

2193번: 이친수

 

 이 문제는 Dynamic Programming, DP를 이용하여 해결할 수 있습니다. 

 

 이친수 성질인

 

   (1) 0으로 시작하지 않는다.

   (2) 1이 연속되지 않는다.

 

를 만족하는 dp를 설정하는 것은 간단합니다. 

 

 dp[n][2]를 dp로 설정합니다. dp[n][0]은 n번째 자리에서 0이 올 수 있는 경우의 수, dp[n][1]은 n번째 자리에서 1이 올 수 있는 경우의 수를 나타냅니다. 

 

 트리 형태로 보시면 이해가 빠릅니다. 

 

 1은 0으로부터 만들어지고 0은 1과 0으로부터 만들어집니다.

 

 즉, 부모 노드가 1이라면 자식 노드는 0만, 부모 노드가 0이라면 자식 노드는 0과 1이 됩니다.

 

 점화식을 나타내면

dp[n][0]=dp[n-1][0]+dp[n-1][1]

dp[n][1]=dp[n-1][1]

 

 그렇다면 n자리 이친수의 수는 어떻게 될까요?

 

 간단합니다 dp[n][0]+dp[n][1]을 해주면 됩니다. 

 

  n자리 이친수의 개수 = dp[n][0]+dp[n][1]

 

n	{dp[n][0], dp[n][1]}	n자리 이친수의 수
1	{0, 1}	1
2	{1, 0}	1
3	{1, 1}	2
4	{2, 1}	3

 

#include<iostream>

using namespace std;

long long dp[91][2] = { 0, };

int main(void) {

	int n;

	cin >> n;

	dp[1][0] = 0;
	dp[1][1] = 1;
	dp[2][0] = 1;
	dp[2][1] = 0; 

	for (int i = 3; i <= n; i++) {
		dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
		dp[i][1] = dp[i - 1][0];
	}

	cout << dp[n][0] + dp[n][1];

	return 0;
}