백준 1904 01타일

계획

• 동적 계획법은 점화식을 세워야 한다고 합니다.
• i번째 (i길이)의 가능한 가짓수는 i-1길이 가짓수 + i-2 가짓수
  • x(i) = x(i-1) + x(i-2)
• i가 짝수면, i-2에서 i로 가는 가능성은 00을 추가하는 방법 밖에 없고, i-1에서 i로 가는 가능성은 1을 추가하는 방법밖에 없음. i가 홀수인 경우는 반대로 마찬가지.
• x(1), x(2)는 각각 1, 2로 초기화 (가능성이 1, 2임)

주의사항

• 입력이 1, 2인 경우 인덱스에러 발생 주의

import sys
N = int(input())
lst = [0] * (N + 1)

if N <= 2:
    print(N)
    exit()
    
lst[1] = 1
lst[2] = 2
for i in range(3, N + 1):
    lst[i] = (lst[i - 1] + lst[i - 2]) % 15746
print(lst[N])