boj9461 파도반 수열 (실버3) - DP

백준 문제 링크

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

9461번: 파도반 수열

 

동적계획법(DP: Dynamic Programming) 

입력크기가 작은 부분의 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서 큰 크기의 문제를 해결하는 방법.

 

 

 

내 풀이

# boj9461 파도반 수열 (DP)

import sys

m = int(sys.stdin.readline())

for i in range(m):
    n = int(sys.stdin.readline())

    # 점화식 세우는 게 중요
    dp = [0] * 101
    dp[1:11] = [1, 1, 1, 2, 2, 3, 4, 5, 7, 9]
    for i in range(11, n+1): # len(arr)이던, n+1이던 실행 시간에 큰 영향 X
        dp[i] = dp[i - 1] + dp[i - 5]
    print(dp[n])

 

https://github.com/yj0903/python_CodingTest/blob/main/Algorithms/DP/boj9461.py

GitHub - yj0903/python_CodingTest: python_problemSolving