[BOJ] 9461번 파도반 수열 (Python)

[BOJ] 9461 파도반 수열 (Python)

9461번: 파도반 수열

• 전형적인 방법은 보텀업방식
• 메모이제이션, 한번 구한 정보를 리스트에 저장하는 것

n은 최대 100까지 주어지니깐 우선 길이가 100인 0으로 초기화된 리스트를 생성

• dp = [0] * 101

규칙을 생각해보면

우선 dp는 초기에 규칙이 없는 조건은 수작업으로 설정을 해주는 경우가 대부분이다.

1, 1, 1, 2, 2

• dp[1] = 1
• dp[2] = 1
• dp[3] = 1
• dp[4] = 2
• dp[5] = 2

뒷 부분을 살펴보면, 아래와 같은 규칙을 가짐

dp[6] = dp[5] + dp[1]

dp[7] = dp[6] + dp[2]

dp[8] = dp[7] + dp[3]

dp[9] = dp[8] + dp[4]

이 규칙을 점화식으로 정리하면,

• dp[i] = dp[i-1] + dp[i-5] (i>5)

n = int(input())
t = [int(input()) for _ in range(n)]
dp = [0,1,1,1,2,2]

for i in range(6, max(t)+1):
    dp.append(dp[i-1] + dp[i-5])

for i in t:
    print(dp[i])

다른 풀이

dp[i] = dp[i-3] + dp[i-2] 의 점화식을 가지는 피보나치 수열로 생각할 수도 있다.

dp = [0] * 101
dp[1], dp[2], dp[3] = 1, 1, 1
for i in range(4, 101):
    dp[i] = dp[i-3] + dp[i-2]

n = int(input())
for i in range(n):
    t = int(input())
    print(dp[t])