[백준] 2193번: 이친수 / 파이썬

문제 링크

---

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

 

풀이 코드

---

n = int(input())

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

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

print(dp[n])

코드 해석

---

경우의 수를 살펴보면

1 자릿수 일 땐 0,1 2개

2 자릿수 일 땐 00,01,10  3개

3 자릿수 일 땐 000,001,010,100,101  5개

4 자릿수 일 땐 0000,0001,0010,0100,0101,1000,1001,1010  8개

 

어라...?

피보나치수열이랑 똑같잖아?

 

그래서 DP를 사용한 피보나치수열로 풀었다.

점화식은 dp[i] = dp[i-1] + dp[i-2] 이다.

 

 

체감 난이도: ★☆☆☆☆