[BOJ 1904] 01타일

문제 출저 : https://www.acmicpc.net/problem/1904

 

풀이:

 

DP문제입니다.

N=1 일때 1

N=2 일때 1,00

N>=3 일때 [N] = [N - 2] + [N - 1]입니다.

 

N>=3일때 점화식이 저렇게 나오는 이유는

N일때의 타일패턴은 N-1 에서 1타일을 추가한 것, N-2에서 00타일을 추가한 것 뿐이기 때문입니다.

 

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