이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 72 번째 글 입니다.
목차
실버3 : 동적계획법 문제이다.
생각
이 문제의 핵심은, 최고자리 숫자가 0 또는 1일 때의 상황을 분리해서 생각해보는 것이다. 이유는 나열하면 금방 알아차릴 수 있다.
| N | 1 | 2 | 3 | |||
|---|---|---|---|---|---|---|
| 0 | X | 00 | X | 000 | X | |
| 1 | O | 01 | X | 001 | X | |
| 10 | O | 010 | X | |||
| 11 | X | 011 | X | |||
| 100 | O | |||||
| 101 | O | |||||
| 110 | X | |||||
| 111 | X | |||||
| 1 | 1 | 2 |
여기서 N이 2 일 때를 생각해보면, 앞자리에 1이 있어야 하고, 그 뒤는 0으로 시작해야 한다. 0으로 시작한 이후에는 이친수가 와야한다. 그럴 경우에 새로운 이친수가 만들어진다. 따라서 N이 증가함에 따라 다음 자리수의 이친수를 만들기 위해서는 최고자리가 0인 상황에서 다음 숫자부터 가지는 이친수를 저장할 필요가 있다.
정의
dp[N][0] : N자리수의 최고자리가 0일 경우 이후 자리수에서 가질 수 있는 이친수의 개수
dp[N][1] : N자리수의 최고자리가 1일 경우 가질 수 있는 이친수의 개수
점화식
dp[N][0] = dp[N-1][0] + dp[N-1][1];
최고자리수가 0일 때, 위의 정의에 맞는 개수를 구하기 위해서는 그 다음 자리의 수가 1인 경우와, 0인 경우가 있다. 따라서 그 두 경우를 모두 더해주어야 내가 원하는 수를 구할 수 있다.
dp[N][1] = dp[N-1][0];
1인 경우에는 무조건 다음 자리수가 0으로 시작하는 이친수를 구해야 하므로 위와 같다.
Code
// 실버3 : 백준 2193번 이친수
#include <iostream>
using namespace std;
int main(){
int N;
long long dp[91][2];
cin >> N;
dp[1][0] = 1;
dp[1][1] = 1;
for (int i = 2; i <= N; i++) {
dp[i][0] = dp[i-1][0] + dp[i-1][1];
dp[i][1] = dp[i-1][0];
}
cout << dp[N][1] << '\n';
}
피보나치 수열
그런데 위의 점화식을 잘 정리하면 우리가 알고있는 피보나치 수열의 형태가 나온다.
\[\begin{align} dp[N][0] + dp[N][1] & = (dp[N-1][0] + dp[N-1][1]) + dp[N][1] \\ & =(dp[N-1][0] + dp[N-1][1]) + dp[N][0] \\ &= (dp[N-1][0] + dp[N-1][1]) + (dp[N-2][0] + dp[N-2][1]) \end{align}\]다이나믹은 끝이 없다.