이친수 - 실버 3 (백준, DP)

import sys

input = sys.stdin.readline
dp = [0]*90
dp[0] = 1
dp[1] = 1
N = int(input())
for i in range(2, N):
  dp[i] = dp[i-2] + dp[i-1]

print(dp[N-1])

규칙을 찾아서 정답을 맞출 수 있었다. dp를 맞춘 게 얼마만인지.. 간단한 문제긴 하지만 굉장히 뿌듯하다.

 

공식은 다음과 같다.

1 = 1

2 = 10

3 = 100 101

4 = 1000 1010 1001

 

위와 같이 증가하는 값을 잘 보면 끝에 붙는 값이 0 혹은 1로 끝나는 걸 알 수 있다.

 

이유는 무조건 앞의 값은 1이고 1은 두 번 반복할 수 없기 때문에 항상 뒤에 0 혹은 01이 붙어야한다.

 

3을 보면 1에 01을 붙인 것과 1에 0을 붙인 값의 모음인 걸 알 수 있다. 

 

4를 보면 3에 0을 붙인 것과 2에 01을 붙인 값이다.

 

그래서 공식은 i-2 + i-1이 성립하게 된다.