[백준/Python] 9461 파도반 수열

[백준/Python] 9461 파도반 수열

정답 코드 및 설명

전체 코드

T = int(input())
p = [0, 1, 1, 1, 2, 2] + [0]*95  

def dp(n):
    if n < len(p) and p[n] != 0: 
        return p[n]
    if n < 1:  
        return 0
    if n < 3:  
        return 1
    if n == 3:  
        return 1
    if n == 4:  
        return 2
    if n == 5:  
        return 2
    for i in range(6, n+1):  
        p[i] = p[i-1] + p[i-5]
    return p[n]

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

파도반 수열은 일정한 규칙에 따라서 삼각형들이 추가 되면서 나선을 형성하는 수열이다.

파도반 수열 처음 몇 항을 보면 1,1,1,2,2,3,4,5,7,9 ... 규칙을 찾을 수 있다

P(N) = P(N-1) + P(N-5) 이라는 점화식을 도출할 수 있고 이를 코드에 적용할 수 있다.

p = [0, 1, 1, 1, 2, 2] + [0]*95 

P(0) to P(5)는 초기 값으로 설정, 나머지는 0으로 초기화한다.

함수 def dp(n): 에 대한 설명

if n < len(p) and p[n] != 0: 
        return p[n]

이미 계산된 값은 바로 반환

if n < 1:  # n이 1보다 작은 경우
        return 0
    if n < 3:  # n이 3보다 작은 경우
        return 1
    if n == 3:  # n이 3인 경우
        return 1
    if n == 4:  # n이 4인 경우
        return 2
    if n == 5:  # n이 5인 경우
        return 2

n이 5 이하 일 경우 반환

for i in range(6, n+1):  # n이 6 이상인 경우 점화식에 따라 계산
        p[i] = p[i-1] + p[i-5]
    return p[n]

n이 6이상이면 점화식에 따라 계산하고 이를 반환한다.

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

주어진 입력 T에 대해 각 테스트 케이스마다 N을 입력받고, dp 함수를 호출하여 P(N)을 계산합니다. 만약 p 배열에 이미 계산된 값이 있다면, 그 값을 바로 반환한다. 그렇지 않은 경우, p 배열의 해당 인덱스까지 값을 채워 나가며 P(N)을 계산