[백준] 9461번 파이썬 (파도반 수열)

1. 문제와 예제

(문제링크: https://www.acmicpc.net/problem/9461)

9461번: 파도반 수열

문제

예제

---

2. 전체 코드

import sys
input = sys.stdin.readline

# 입력 받기
T = int(input().rstrip()) # 테스트 케이스 수
lst = [0, 1, 1, 1, 2, 2] # P(N) 리스트
cnt = 5 # (리스트 길이) - 1

for _ in range(T):
    N = int(input().rstrip()) # P(N)의 N
    while (N > cnt):
        lst.append(lst[cnt] + lst[cnt-4])
        cnt += 1

    # 결과 출력하기
    print(lst[N])

---

3. 코드 해설

P(N) 규칙

다이나믹 프로그래밍을 활용해야 하는 문제다. 즉, P(N)의 규칙을 찾아 점화식을 풀듯이 구하면 된다.

우선 리스트의 1부터 5까지는 규칙이 없이 나오는 수이므로 미리 집어넣어 주고 (lst[N]이 P(N)을 나타내도록 lst[0]=0을 추가했다) 그 뒤의 P(N) 리스트 값은 필요하면 구해내는 방식을 사용하였다.