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

Coding Test/Python

lim.dev 2024. 1. 28. 12:46

1904번: 01타일

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이

www.acmicpc.net

아이디어

dp 문제이다.

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