BOJ - 1904

백준 문제 링크
01타일

❓접근법

1. 타일이 1개 - 1가지
   타일이 2개 - 2가지
   타일이 3개 - 3가지
   타일이 4개 - 5가지
   이를 이용해 점화식을 세워보면
   a[n] = a[n-1] + a[n-2]로 알 수 있다.
2. 위 점화식을 이용해 DP에 저장 후 DP[N]을 출력하면 끝!

👌🏻코드

N = int(input())


if N == 1:
    print(N)
else:
    DP = [0] * (N+1)
    DP[1] = 1
    DP[2] = 2
    
    for i in range(3, N+1):
        DP[i] = (DP[i-1] + DP[i-2]) % 15746

    
    print(DP[N])