TIL 45 | 파도반수열 (백준 9461 python) - 동적계획법

🚀문제 바로가기

접근방식

1) 규칙찾기 :
첨부된 그림처럼 변의 길이 1인 정삼각형을 시작으로 삼각형을 그려나간다. 가장 긴 변의 길이가 갱신되면 그것을 크기로한 정삼각형을 만든다. 이 과정에서 규칙을 찾아내어 P(N)을 구해야 한다. n번째 정삼각형은 n-1번째 정삼각형 변의 길이와 n-5번째 정삼각형 변의 길이의 합이라는 규칙이 있다. 이를 통해 점화식을 도출해내면 다음과 같다. Pn=P(n-1)+P(n-5)

2) DP활용 :
문제에서 주어진 P(1)~P(10)까지의 결과 값을 저장하여 이전의 계산된 값을 가지고 다음 값을 계산해나가는 다이나믹프로그래밍(DP)를 구현할 것이다. 이를 이론적으로는 다이나믹프로그래밍 바텀업 방식이라고 한다.

3) 테스트 케이스 중 가장 큰 값까지 파도변을 구해 미리 결과를 저장함으로써 값이 투입될 때마다 계산될 필요가 없도록 한다.

t = int(input())
test_case = []
max_test_case = 0

for _ in range(t):
    n = int(input())
    test_case.append(n)
    max_test_case = max(max_test_case,n)
rst = [1, 1, 1, 2, 2, 3, 4, 5, 7, 9]

for i in range(10,max_test_case): #rst에 없는 값부터 반복
    Pn = rst[i-1]+rst[i-5]
    rst.append(Pn)

for n in test_case:
    print(rst[n-1]) #nth 값은 rst[n-1]에 저장되어있다.