[C++] 백준 - 1904 : 01타일

문제 링크

1904번: 01타일

 

풀이 ) DP

  앞에 포스팅한 이친수와 같은 풀이이다.

  시작할 수 있는 가짓수는 2가지다. 1로 시작하거나 00으로 시작할 수 있다.

  따라서 점화식 memo[n] = memo[n-1] + memo[n-2]이다.

 

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

int memo[1000002] = {0, 1, 2, };

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

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

    printf("%d\n", memo[n]);
    return 0;
}