[DP] 백준 2193 이친수

문제링크 www.acmicpc.net/problem/2193

 

이게 왜 피보나치인 지 궁금해서 질문 게시판 보고 정리했다

 

 

[답코드]

import sys
input=sys.stdin.readline
 
n=int(input())
fib=[1, 1]
 
for i in range(n-2):
    fib.append(fib[-1]+fib[-2])
print(fib[-1])

 

[풀이법]

 

fib(n)=fib(n-1)+fib(n-2)가 나오는 이유는

 

① 뒤에 0은 아무데나 붙을 수 있다 fib(n-1) 수열에 0을 붙이면 된다

 

② 뒤에 1이 붙는 수열은 사실상 2자리가 고정돼있다고 생각해야한다.

1이 연속될 수 없으므로 fib(n-2)의 수에 01이 붙어 fib(n)을 구성한다고 생각해야 한다.

 

 

 

코테 풀다보면 나빼고 다 천재인 느낌이다