백준 알고리즘] 2193 : 이친수

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

알고리즘이 복잡한 건 없다.

알고리즘에 대해서 지식이 전무한 사람은 모든 케이스를 테스트하려고 하지만,

기본적으로 숫자길이를 확장해나가는 것에 있고,

이전의 값을 바탕으로 답을 구해나갈 수 있다는 점을 감안하면 쉽게 풀어낼 수 있다.

숫자의 자릿수가 늘어날 때마다, 이전에 판단했던 이친수에서

얼마나 많은 이친수를 만들어낼 수 있는지에 관한 점화식을 작성하기만 하면 된다.

복잡한 2차원 테이블을 작성하는 것도 아니라서 비교적 쉬운 편이다.

유의해야 하는 점 하나는,

n값이 커지면 int 범위를 넘어가기 때문에

여기서 long long int를 사용했던 것처럼 이를 담아낼 수 있는 적합한 자료형을 사용해야 한다는 점이다.

#include <iostream>
using namespace std;
 
int main(void){
 
    long long int n;
    long long int 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]; 
    return 0;
}