[백준 2193][C++] 이친수

[문제보기]

 2193. 이친수

2193번: 이친수

 

[풀이과정]

이 문제는 4자리까지만 손으로 적어보면 바로 점화식이 나오는 문제이다. 

1이 연속으로 나오는 것만 조심하면서 각 자리수의 이친수를 찾으면 되기 때문에, 이전에 나온 이친수에서

마지막이 1이 아닌 0으로 끝나는 이친수는 뒤로 1, 0이 붙을 수 있기 때문에 경우의 수가 2가 되고, 

마지막이 1인 이친수는 무조건 0만 올수 있기 때문에 경우의 수가 1이 된다.

이렇게 늘어나는 숫자를 생각하면 피보나치 수가 형성이 되는 것을 볼 수가 있어

점화식도 피보나치 수를 구하는 식으로 사용을 하면 된다. 

[소스코드]

#include <iostream>
using namespace std;

int main(){
    long long dp[91] = {0};
    dp[1] = 1;
    dp[2] = 1;
    for(int i = 3; i<91; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }

    int n;
    cin >> n;
    cout << dp[n];
}

 

[해결 과정 중 실수한 부분]