1904번: 01타일 (DP) - Fastcampus

www.acmicpc.net/problem/1904

1904번: 01타일

# dp[i]: (길이 i) 타일을 만드는 경우의 수
# dp[i] = dp[i-2] + dp[i-1]

def run(N):
    dp = [0] * max(N+1, 3)  # 최소사이즈 dp[2]까지 설정
    dp[1] = 1
    dp[2] = 2
    for i in range(3, N+1):
        dp[i] = (dp[i-1] + dp[i-2]) % 15746
    return dp[N]


N = int(input())
print(run(N))