백준(BOJ) #9461 파도반수열 파이썬(Python)

파도반수열…?

---

개념이 조금 낯설 뿐, 피보나치와 비슷하다는 힌트를 보고 자연스럽게 점화식?을 생각하게 되었다.

하지만! 그냥 늘어진 숫자만 보고서 어떤 규칙을 찾는담? 하고 막막한 생각이 들었다.

# 직접적인 관계 찾아보기
P(4) = P(1) + P(3)
P(5) = P(4)
P(6) = P(5) + P(3)
P(7) = P(6) + P(2)
P(8) = P(7) + P(1)

결국

---

직접적인 관계는 아니지만! 간접적인 관계가 있음을 확인할 수 있었다.

n > 5에서는, P(n) = P(n-5) + P(n-1)

DP와 메모이제이션을 이용해서 구현하기

---

피보나치 수열도 마찬가지로, 이미 구한 값을 또! 재귀로 호출할 필요 없이 메모이제이션을 사용해서,

한 번 부른 값을 기억해두면 시간초과를 막을 수 있다.

import sys
# 결국 파도반 수열은 P(n) = P(n-1) + P(n-5)
waves = [0]*101
waves[1] = 1
waves[2] = 1
waves[3] = 1
waves[4] = 2
T = int(sys.stdin.readline().rstrip())
def wave(n):
    if n < 5:
        return waves[n]
    if waves[n] == 0:
        waves[n] = wave(n-1) + wave(n-5)
    return waves[n]

for tc in range(T):
    N = int(sys.stdin.readline().rstrip())
    print(wave(N))

Uploaded by N2T