[백준][동적 계획법 1] No.9461_파도반 수열 01

 

9461번: 파도반 수열

아는 수학과에게 물어보았더니 실제 있는 수열이라고 한다.

백준에서 문제를 출제하기 위해 임의로 만든 수열인 줄 알았지만 아니었다.

 

파도반 수열은 '첫 정삼각형 변의 길이는 1이다. 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 다음과 같은 과정으로 정삼각형을 계속 추가한다. 이때의 가장 긴 변의 길이의 집합이다'로 정의할 수 있다.

위에 그림에서 왼쪽이 파도반 수열이고, 오른쪽이 피보나치 수열(흔히 말하는 황금비 수열)을 도식화한 것이다.

얼핏 보아도 대충 비슷한 느낌임을 알 수 있다. 정의가 어렵지 단순히 항을 나열해보면 아래와 같다.

 

# 피보나치 수열
# 1 1 2 3 5 8 13 21

# 파도반 수열
# 1 1 1 2 2 3 4 5 7 9

피보나치 수열이 a_n = a_n-1 + a_n-2 또는 a_n+2 = a_n+1 + a_n로 쓸 수 있고,

파도반 수열은 a_n = a_n-2 + a_n-3 또는 a_n+3 = a_n+1 + a_n로 쓸 수 있다.

피보나치 수열에 대한 설명은 https://miny-genie.tistory.com/79에서 확인할 수 있다.

여기서는 파도반 수열을 기반으로 동적 프로그래밍을 연습하겠다.

 

# ---------- Function ----------
def padovan(N):
    #padovan_list[1], padovan_list[2], padovan_list[3] = 1, 1, 1
    if N == 1 or N == 2 or N == 3:
        return 1
    
    if padovan_list[N] != 0:
        return padovan_list[N]
    
    padovan_list[N] = padovan(N-2) + padovan(N-3)
    
    return padovan_list[N]

# ---------- Main ----------
caseT = int(input())

for _ in range(caseT):
    N = int(input())
    padovan_list = [0] * (N+1)
    print(padovan(N))

padovan(N) 함수를 살펴보면 1, 2, 3항은 전부 1이므로 1로 초기화한다.

그후 padovan 리스트의 N번째 인덱스 값이 비어있다면 padovan(N-2)와 padovan(N-3)을 호출한다.

10번쨰 코드인 "padovan_list[N] = padovan(N-2) + padovan(N-3)" 부분이 핵심이다.

리스트( [ ] ) 기호와 함수 매개변수( ( ) ) 기호를 헷갈리지 말자.