[백준/dp] 1904번: 01타일 (실버3, python)

https://www.acmicpc.net/problem/1904

1904번: 01타일

아이디어

dp 문제이다. 

N	갯수
1	1
2	2
3	3
4	5
5	8
6	13
. . .

N을 1씩 증가시키면서 구하면 아래와 같은 규칙을 찾을 수 있다.

만들 수 있는 길이가 N인 모든 2진 수열의 개수 = N-1인 모든 2진 수열의 개수 + N-2인 모든 2진 수열의 개수

즉 dp[n] = dp[n-1] + dp[n-2] 이다.

 

전체 코드

N = int(input())
dp = [0] * (N + 2)

dp[1], dp[2] = 1, 2

for i in range(3, N + 1):
    dp[i] = (dp[i-1] + dp[i-2]) % 15746

print(dp[N])