python 백준 2193 이친수

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

2193번: 이친수

 

문제 ? 이친수를 만족하는 숫자의 개수를 찾아라

접근법 

- 첫번째는 부분문자열로 일일이 다 검색을 해볼려했는데 자리수의 개수가 90인걸 보고 2**90을 볼수는 없으니 포기했다 ㅋㅋㅋ

- 두번째로는 결국 종이에 써보다가 발견한 건데 신기하게도 피보나치수열을 만족한다는 것이였고

 - 이 문제는 다이나믹 프로그래밍으로 연결된다 결구 f(n) = f(n-1) + f(n-2)로 문제를 풀 수 있게 된다

 - 그리고 다른 동기가 접근 한 방법으로는 0,1을 나누어 dp로 접근하는 방법도 있어서 매우 신기한 경험이었다.

- dp는 너무 어렵지만 계속해서 직관력을 키워야겠다

import sys
#sys.stdin = open("inputs.text")


n = int(sys.stdin.readline())
dp = [0] * (n+1)

dp[0] = 0
dp[1] = 1

for i in range(2,n+1):
  dp[i] = dp[i-1] + dp[i-2]

print(dp[n])