[Python] 백준 1904번 01타일

문제

[Python] 백준 1904번 01타일 성공

입력

• 첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

출력

• 첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

입력 예제

4

출력 예제

5

문제 풀이

• 조건을 살펴보면 i번째 가능한 타일의 개수는 (i - 1)의 개수 + (i - 2)의 개수이다.
• 따라서 점화식은 아래와 같다.

dp[i] = (dp[i - 1] + dp[i - 2]) % 15746

•  

코드

n = int(input())
dp = [0] * 1000001
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])