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

문제 링크

2193번: 이친수

 

풀이 ) DP

  문제에서 주어진 이친수는 01로 끝나거나 0으로 끝날 수 있다.

  01로 끝나는 경우는 n-2자리 이친수의 뒤에 01을 붙인 경우로 볼 수 있고

  0으로 끝나는 경우는 n-1자리 이친수의 뒤에 0을 붙인 경우로 볼 수 있다.

  따라서 이 때의 점화식은 memo[n] = memo[n-1] + memo[n-2]의 꼴이 됨을 알 수 있다.

#include <cstdio>
#include <algorithm>
using namespace std;

long long memo[92] = {0, 1, 1, };

int main(void)
{
    int n;
    scanf("%d", &n);

    for(int i = 3; i <= n; ++i)
        memo[i] = memo[i-1] + memo[i-2];

    printf("%lld\n", memo[n]);
}

 

착오 )

  처음에는 끝이 아닌 앞을 보고 시작했었다.

  그런데 이럴 경우 2자리 이상일 때 10으로 시작하기는 하지만

  이후 3번째 자리부터는 0으로 시작할 수 있기 때문에 이전에 구한 값을 이용할 수 없어서 불가능했다.