[PS] 백준 1904번: 01타일

|

문제

내가 이해한 문제 내용

타일 100이 주어졌을 때 크기 $N$의 타일을 만들 수 있는 경우의 수를 구하여라.

접근 방식

DP로 접근하다가 규칙성을 찾아서 바로 피보나치 돌렸다.

어려웠던 점 & 배운 점

나눠야 하는 수를 보지 못함, 문제 제대로 읽자.

시간복잡도

$O(N)$

코드

#include <cstdio>

long long fibo[1000001];
const long long mod = 15746;

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

    fibo[0]=1;
    fibo[1]=1;
    for(int i=2; i<=n; i++)
        fibo[i] = (fibo[i-1]%mod+fibo[i-2]%mod)%mod;

    printf("%lld",fibo[n]);
    return 0;
}