백준 1904번 : 01타일 (C언어)

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

1904번: 01타일

Code:

#include <stdio.h>
 
int main()
{
    int n;
    scanf("%d", &n);
    int dp[1000001] = { 0, };
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++)
    {
        dp[i] = (dp[i - 1] + dp[i - 2])%15746;
    }
    printf("%d", dp[n]);
    return 0;
}
 

문제풀이 :

기본적인 다이나믹 프로그래밍이다. 피보나치 수열처럼 [i]가 [i-1]과 [i-2]의 합으로 표현됨을 알 수 있다.