[백준] 2193번 이친수

 

해당 문제는 DP 문제입니다.

 

접근법

- 규칙성 찾기

- 점화식 형태 구현

- 조건을 만족하려면 100, 101 형태를 지켜야함.

 

1 : 1
2: 10
3 : 100, 101
4 : 1000, 1001, 1010
5 : 10000, 10001, 10010, 10100, 10101

→ 점화식 : dp[i] = dp[i-1] + dp[i-2]

 

 

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])