[파이썬, Python] 백준 2193: 이친수

문제

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

2193번: 이친수

코드

n = int(input())

dp = [0] * (n + 1)
dp[1] = 1

for i in range(2, n+1):
    dp[i] = dp[i-2] + dp[i-1]

print(dp[n])

설명

규칙을 찾아서 해결하는 dp 문제였다.

n = 1 일 때, [1]
n = 2 일 때, [10]
n = 3 일 때, [100][101]
n = 4 일 때, [1000][1001][1010]
n = 5 일 때, [10000][10001][10010][10100][10101]

이렇게 이전의 수에 규칙에 따라 1 혹은 0이 붙는 모습을 볼 수 있다.

따라서 dp식을 작성하면 dp[n] = dp[n-1] + dp[n-2]가 된다.