백준 2193 파이썬 (이친수)

문제 : https://www.acmicpc.net/problem/2193

💻 Code

n = int(input())

dp = [[0 for _ in range(2)] for _ in range(91)]
dp[1] = [0,1]
dp[2] = [1,0]

for i in range(3, 91):
    dp[i][0] = dp[i-1][0] + dp[i-1][1]
    dp[i][1] = dp[i-1][0]

print(sum(dp[n]))

끝자리 수를 활용해 점화식을 세워보았다.

n=1 -> 1
n=2 -> 10
n=3 -> 100, 101
n=4 -> 1000, 1001, 1010

0으로 끝날 경우 뒤에 0과 1이 올 수 있으므로 2개가 추가됨 (파란 선)
1로 끝날 경우 뒤에 0밖에 오지 못하므로 하나만 추가됨 (빨간 선)

따라서 점화식은

dp[i][0] = dp[i-1][0] + dp[i-1][1]
dp[i][1] = dp[i-1][0]

뒤늦게 알았지만 그냥 1차원 리스트로 dp[n] = dp[n-1] + dp[n-2]로 풀면 된다는..