[DP] 백준 2193번 - 이친수

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

2193번: 이친수

백준 DP 연습문제다.

행이 1~N, 열이 0, 1로 이루어진 표를 그려 문제를 풀었다.

행은 길이를, 열은 0또는 1로 끝나는 해당 길이의 이친수의 개수를 의미한다.

 

N번째 이친수를 구하려면 그 이전의 이친수들에 0 또는 1을 추가하는 것이므로, 이전 답을 현재 답을 구하는데 활용하는 전형적인 DP 유형이다.

 

점화식은 현재 길이 N이며 0으로 끝나는 이친수의 개수를 DP[N][0]으로, 1로 끝나는 이친수의 개수를 DP[N][1]로 정의했을 때,

DP[N][0] = DP[N-1][0] + DP[N-1][1];

DP[N][1] = DP[N-1][0];

로 정의할 수 있다.

 

즉, 1로 끝나는 이친수는 0밖에 추가 못하므로 길이가 1 짧은 이친수 중 0으로 끝나는 것의 개수와 같다. (1로 끝나는 것은 1로 끝날 수 없기 때문.)

또한 0으로 끝나는 이친수는 0 또는 1로 끝날 수 있으므로, 길이가 1 짧은 이친수 중 0과 1로 끝나는 이친수들의 개수의 합과 같다.

 

근데 점화식도 잘 세우고 돌렸는데 틀렸다고해서 왜그런가 했더니 생각이상으로 이 숫자가 큰 N의 테스트 케이스에서 int의 값을 벗어나나보다. long long DP[maxlen][2]로 선언하고 돌렸더니 맞았다는 메시지가 떴다.

 

아래는 소스코드.

 

#include <iostream>
#include <algorithm>
#define maxlen 90 + 1
using namespace std;
long long DP[maxlen][2];
int N;
int main(){
    cin >> N;
    DP[1][0] = 0; 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][0] + DP[N][1] << '\n';
    return 0;
}