11726번 Python

과거에 풀어보긴 해서 문제에 대한 이해가 어렵지는 않았고 점화식을 바로 구해보았다.

 

1 -> 1
2 -> 2
3 -> 3
4 -> 5

위의 형태는 피보나치 수열 형태로 첫째항과 둘째항이 1이면 그 다음항은 그것의 값들을 의미하는 걸 말한다. DP 정리에서도 잠시 이야기 했었다.

 

import sys

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

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

print(dp[n])

어렵게 구하지 않았고 바로 답을 도출해낼 수 있었다.