[BOJ 2193] 이친수 (Python)

문제

이친수

---

문제 해설

처음에 dfs로 풀었으나, 시간 초과로 인해 DP로 풀게 된 문제입니다.

n = 3
100, 101
n = 4
1000, 1001, 1010
n = 5
10000, 10001, 10010, 10100, 10101

n의 경우의 수를 조금씩 나열하다 보면 규칙이 보입니다.
n은 n-1에서 0, n-2에서 01을 붙인 것입니다.
따라서 점화식은 dp[n] = dp[n-1] + dp[n-2] 입니다.

풀이 코드

n = int(input())
dp = [0] * 91
dp[1] = dp[2] = 1

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

---