백준 #2193. 이친수 / C++ / Dynamic Programming

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

2193번: 이친수

문제에서 제시한 이친수의 조건

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

2. 1이 두 번 연속해서 나타나지 않는다.

 

N이 1일 경우부터 차례차례 생각해보면 금방 해답을 구할 수 있다.

 

N = 1일 때 이친수는 1                              (0 은 불가능)

N = 2일 때 이친수는 10                            (11은 불가능)

N = 3일 때 이친수는 100, 101

N = 4일 때 이친수는 1000, 1001, 1010

 

즉,

 

N = 1일 때 이친수는 1 

N = 2일 때 이친수는 10

 

N = 2일 때 이친수는 10

N = 3일 때 이친수는 100, 101

 

N = 3일 때 이친수는 100, 101

N = 4일 때 이친수는 1000, 1001, 1010

 

 

다음으로 알 수 있는 것은

1. N-1자리 이친수에서 뒤에 1이나 0을 붙여 N자리 이친수를 나타낼 수 있다.

2. 1은 두 개 이상 연속할 수 없으니 N-1자리 이친수가 1로 끝난다면 N자리 이친수가 되려면 0밖에 붙을 수 없다.

3. 0으로 끝나는 N-1자리 이친수는 뒤에 0과 1을 붙여 N자리 이친수를 만들 수 있다.

 

따라서, N마다 끝자리 수가 0일 경우와 1일 경우를 세면 된다.

 

count[91][2] 배열의 행은 N, 열 2개 중 첫 번째 열은 끝자리 수가 0일 때, 두 번째 열은 끝자리 수가 1일 경우를 센다.

ex. count[5][0] : N = 5일 때 끝자리 수가 0인 수의 개수

 

이 식들을 토대로 다음과 같은 점화식을 도출할 수 있다.

count[i][0] = count[i-1][0] + count[i-1][1];

count[i][1] = count[i-1][0];

 

다음은 소스코드이다.

#include <iostream>
using namespace std;

int main() {

	int n;
	long long count[91][2] = { {0, 0}, {0, 1}, {1, 0} }; //0 count, 1 count

	cin >> n;

	for (int i = 2; i <= n; i++) { //dynamic programming
		count[i][0] = count[i - 1][0] + count[i - 1][1];
		count[i][1] = count[i - 1][0];
	}

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

	return 0;
}