문제
나의 답안
n=int(input())
dp=[]
dp.append(0)
dp.append(1)
for i in range(2,n+1):
dp.append(dp[i-2]+dp[i-1])
print(dp[n])접근 방법
- dp문제, 문제의 조건에 따라 길이가 2이상이면 앞 두자리는 10로 고정된다.
- n=2, 10
n=3, 10+[0,1] =>[100,101]
n=4, 10+[00,01,10] => [1000,1001,1010] - n=4일때, n=3 숫자(뒤에서 2자리) 2개, n=2의 1개의 숫자의 조합
- 따라서 길이 n인 이친수
dp[n]=dp[n-2]+dp[n-1]라는 점화식을 도출해낼 수 있다.
어제 풀었던 피보나치 수2와 유사한 문제이다.
