백준 2193번 파이썬 문제풀이(DP - 이친 수)

---

위 문제도 DP문제 이기에 점화식만 찾으면 쉽게 해결할 수 있는 문제이다. 다음을 보면 N이 1~6 일때의 이친수들을 보여주는데 개수의 증가가 1-1-2-3-5-8... 이런식으로 증가하기 때문에 피보나치 수열이라는 것을 알 수 있다.

	1	2	3	4	5	6
1	1	10	100	10000	10000	100000
2			101	1010	10100	101000
3				1001	10010	100100
4					10001	100010
5					10101	101010
6						100001
7						101001
8						100101

 

N = int(input())

dp = [1 for _ in range(N + 1)]

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

print(dp[N])