백준 2193번 이친수 파이썬 풀이

Python

[Python] 백준 알고리즘 온라인 저지 2193 이친수

2193 이친수

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

2193번: 이친수

문제에 제시된 조건을 만족하는 n을 작은 수부터 계산해보니 쉽게 점화식을 만들 수 있었다.

---

소스코드

import sys
input = sys.stdin.readline

n = int(input())
dp = [0, 1, 1]

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

print(dp[n])

---

풀이

자릿수 n을 작은 수부터 생각해보면

n=1 -> 1개 (1)

n=2 -> 1개 (10)

n=3 -> 2개 (100, 101)

규칙적으로 0과 1을 늘려가며 개수가 늘어난다

이를 활용하여 점화식을 만들면 dp[n] = dp[n-2] + dp[n-1]의 식이 성립된다.

---

풀이 결과

2193 풀이 결과