[백준/DP/2193] 이친수

이미지 클릭시, 문제로 이동됩니닷 :)

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

// 피보나치
n = (n-2) + (n-1)

 

테스트 케이스를 구해 피보나치임을 알 수 있었다.

 

import sys
input = sys.stdin.readline

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

print(dp[n-1])