[백준]Baekjoon2193(Dynamic Programming)

먼저 이친수가 한자리 일때는 첫자리는 1 밖에 될 수 없으므로 memo[1] = 1,

두자리 일 떄는 1 뒤에는 0 이 나와야하므로 memo[2] = 1 이다.

이친수의 개수를 구하기 위한 점화식이 무엇인지에 대해 생각해보자.

N번째 수가 0이 나오는 경우는

N-1 이친수의 갯수와 같다. 왜냐하면 N-1자리의 모든 이친수들은 뒤에 0을 가질 수 있기 때문이다.

1이 나오는 경우는 N-2의 길이를 가지는 이친수의 갯수와 같은데

N-1이친수가 0이 나오는 갯수만큼 N번째 이친수에서 1이 나오기 때문이다 

고로 memo[N] = memo[N-1] + memo[N-2]이다.

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

long long memo[91];
int main()
{
	memo[0] = 0; memo[1] = 1; memo[2] = 1;
	int N;
	cin >> N;
	for (int i = 3; i <= N; i++)
		memo[i] = memo[i - 2] + memo[i - 1];
	cout << memo[N] << '\n';
}

좀더 직관적인 방법으로 풀 수도 있다.

이중배열을 사용하여 N번째 자릿수에 나올 수 있는 0의 갯수와

1이 나올 수 있는 갯수를 따로 계산하는것이다.

N번째 자리에 올 수 있는 0의 갯수는 N-1번째 자리에 오는 0의 갯수와 1의 갯수를 모두 합한 것이고

1의 갯수는 N-1번째 자리에 오는 0의 갯수와 같은 수가 될 것이다.

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

long long memo[91][2];
int main()
{
	memo[0][0] = 0; memo[0][1] = 0; 
	memo[1][0] = 0; memo[1][1] = 1;
	memo[2][0] = 1; memo[2][1] = 0;
	int N;
	cin >> N;
	for (int i = 3; i <= N; i++) {
		memo[i][0] = memo[i-1][0] + memo[i-1][1];
		memo[i][1] = memo[i-1][0];
	}
	cout << memo[N][0] + memo[N][1] << '\n';
}