[백준 2193] 이친수 - 피보나치 수열

 

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

1. 코드

n = int(input())

dp = [1]*(n)

for i in range(2,n) :

  dp[i] = dp[i-1] + dp[i-2]

print(dp[n-1])

 

n = 1  :  [ 1 ] = 1

 

n = 2  :  [ 10 ] = 1

 

n = 3  :  [ 100, 101 ] = 2

 

n = 4  :  [ 1000, 1010, 1001] = 3

 

n = 5  :  [ 10000, 10101, 10010, 10001, 10100] = 5

 

 

....

 

 

n 을 계속 구해가다 보면 피보나치 수열과 똑같음을 알 수 있다.

 

 

 

2, 주의사항

 

너무 멀리 돌아가지 말자

 

앞선 문제들처럼 0으로 끝나는 경우와 1로 끝나는 경우를 따로 고려하여 규칙을 찾으려고 했으나

 

정답은 가까이에 있었다.