백준 9461번 파도반 수열 Python 풀이

백준 9461번 파도반 수열 Python

문제 설명

문제

정삼각형을 나선형으로 붙여나가면서 외곽에 남는 가장 긴 변의 길이를 기록한 수열을 파도반 수열이라고 합니다. 첫 10개의 값은 다음과 같습니다.

$$ 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 $$

이 수열의 \( N \)번째 값을 구하는 프로그램을 작성해야 합니다. 입력으로 테스트케이스의 수 \( T \)가 주어지고, 각 테스트케이스마다 \( N \)이 주어집니다. \( 1 \leq N \leq 100 \)입니다.

테스트케이스

예제 입력
2
6
12

예제 출력
3
16

문제 해설

• 정삼각형을 하나씩 붙일 때마다 외곽에 남아 있는 가장 긴 변의 길이가 일정한 규칙을 따릅니다.
• 첫 세 변은 모두 길이가 1입니다. 그다음은 이전 결과와 5번째 이전 결과를 더한 값이 됩니다.
• 예를 들어 6번째 변은 5번째(2)와 1번째(1)를 더해서 3입니다.
• 이렇게 나선의 성질 때문에 중간의 변 일부가 사라지면서 이전 값과 5번째 이전 값의 합이 현재의 길이가 됩니다.

아이디어

• 핵심은 동적계획법(DP)입니다.
• \( P(N) \)을 구하기 위해서는 이전에 계산한 값들을 이용해야 합니다.
• 점화식(관계식)은 다음과 같습니다.

$$ P(n) = P(n-1) + P(n-5) \quad (\text{단 } n\ge6) $$

• 나선형으로 삼각형을 붙이면, 바로 이전에 붙인 삼각형의 긴 변과, 5단계 전에 붙였던 삼각형의 긴 변이 새 외곽 경계가 됩니다.
• 그 두 변의 길이를 합치면 새로 붙일 삼각형의 변 길이가 됩니다.
• 이렇게 하면 \( N=6 \)부터 규칙적으로 계산할 수 있습니다.

전체 코드

코드

N=int(input())

arr=[]
arr.append(1)
arr.append(1)
arr.append(1)
arr.append(2)
arr.append(2)
arr.append(3)
arr.append(4)
arr.append(5)
arr.append(7)
arr.append(9)

for i in range(10,100):
    arr.append(arr[i-5]+arr[i-1])

for i in range(N):
    m=int(input())
    print(arr[m-1])

코드 설명

• arr[]는 파도반 수열을 저장하는 리스트입니다. 크기는 100개까지 계산합니다.
• 처음 10개의 값은 문제에서 주어진 대로 직접 초기화합니다.
• for문으로 \( i=10 \)부터 \( 99 \)까지 점화식을 이용해 계산합니다.
• 테스트케이스 개수를 입력받고, 각 테스트케이스마다 \( m \)을 입력받아 arr[m-1]을 출력합니다.

결론

• 입력 크기가 작고 점화식이 명확하므로 동적계획법으로 풀면 됩니다.
• 0부터 시작하는 리스트 인덱스에 주의해야 합니다.
• 점화식의 의미를 이해하고 구현하면 됩니다.