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

 

 

 

 

파도반 수열을 토대로 N번째 정삼각형의 변의 길이를 구하는 문제이다.

 

P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11
1	1	1	2 (1+1)	2	3 (1+2)	4 (1+3)	5 (1+4)	7 (5+2)	9 (7+2)	12 (9+3)

 

예시 그림을 이용하여 위 표를 작성해보았고, 이를 토대로 다음과 같은 점화식을 도출할 수 있었다!

 

P[n] = P[n-1] + P[n-5]

 

주목했던 부분은 P6부터 모든 항이 바로 직전 항인 [n-1] 과 5회 전 항인 [n-5]의 합으로 구성되어 있다는 것을 발견했다.

다만 이는 n-5 식을 포함하는 만큼 P1~P5까지는 해당되지 않는데, 이러한 부분은 그냥 처음에 동적 배열 선언 시 초기항으로 부여해놓는 식으로 설정하였다. (어차피 항 개수 몇 개 되지도 않으니..)

 

import sys

T = int(input())
arr = [0, 1, 1, 1, 2, 2]
for i in range(6, 101):
    arr.append(arr[i-1] + arr[i-5])

for _ in range(T):
    N = int(sys.stdin.readline().strip())
    print(arr[N])

 

사실 처음에는 위 코드의 arr을 arr=[1,1,1,2,2] 로 설정하여 인덱싱마다 1을 빼는 등의 후처리를 해줬었는데, 배열 인덱스 처리 과정에서 계속 틀린 답이 나와서 그냥 위와 같이 1-based indexing을 사용하도록 앞에 0번째 원소에 0을 삽입하여 arr = [0, 1, 1, 1, 2, 2] 로 초기화하였다.

 

반복문의 범위는 range(6, 101)로 설정하여 배열의 인덱스 범위를 1부터 100까지 스케일링 하였음

마지막에는 원래 arr[N-1] 원소를 추출하는 거였지만, 1-based indexing으로 바꿈으로써 arr[N]으로 변경하였다.