[동적계획법/DP] 백준 9461 파도반 수열 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

9461번: 파도반 수열

 

 

 

2. 문제 풀이

 정삼각형이 나선을 그리며 변의 길이가 늘어납니다. 늘어나는 변의 길이를 '파도반 수열'이라고 할 때, N번째 수를 구해야 합니다.

 

1	2	3	4	5	6	7	8	9	10
1	1	1	2	2	3	4	5	7	9

 문제에서 주어진 P(1) ~ P(10)을 보면 규칙이 보이지 않지만, 좀 더 나열하면 보입니다.

 P(6) 이후로 P(i-1) + P(i-5)의 규칙이 나타납니다.

 

11	12	13	14	15	16	17	18	19	20
3+9	4+11	5+15	7+20	9+27	12+36	15+48	...

 

 

2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

[Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

 피보나치 수열과 마찬가지로, DP로 구현해줍니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

T = int(input())
cache = [1, 1, 1, 2, 2, 3] #파도반 수열

def sail(n):
    #n이 cache에 없을 경우, n까지 수열 구함
    while n > len(cache)-1:
        cache.append(cache[len(cache)-5]+cache[len(cache)-1])

    #n이 cache에 있을 경우
    return cache[n-1]

for _ in range(T):
    N = int(input())
    print(sail(N))

 테스트 케이스 T번 반복해서 파도반 수열을 구합니다. 매번 다시 구하지 않고, cache에 저장해두고 불러와서 사용합니다. 이전 테스트케이스에서 구한 n보다 작으면 예전에 구해둔 걸 출력하고, n이 더 크면 추가해서 구합니다.

 물론, 최악의 경우를 고려해서 N을 100까지 구해놓고 푸셔도 무관합니다.