[파이썬, Python] 백준 1904: 01타일

문제

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

1904번: 01타일

코드

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])

설명

경우의 수에 대해서 생각을 해보아야 한다.

우선 길이가 1인 경우는 1이 들어가는 1가지 경우밖에 없다.
길이가 2인 경우는 00 과 11 밖에 없다.
길이가 3인 경우는 길이 2의 00 과 11 앞에 앞뒤로 1을 붙이는 경우밖에 없다.
길이가 4인 경우는 길이 2의 00 과 11 앞에 00을 붙이는 경우와 11을 붙이는 경우가 있고,
길이 3의 앞뒤로 1을 붙이는 경우가 있다.

dp[1] = 1 { (1) }
dp[2] = 2 { (11) (00) }
dp[3] = 3 { (111) (001) (100) }
dp[4] = 5 { (1111) (0000) (0011) (1100) (1001) }

즉, dp[n] = dp[n-1] + dp[n-2] 가 된다.

문제는 결괏값에 15746으로 나눈 나머지를 출력하라고 했지만,
이렇게 되면 dp값이 과하게 커지므로 계산 과정에서 미리 처리를 해서 넣어주도록 하자.