[BOJ / 파이썬] 9461: 파도반 수열

백준 / BOJ / Python / 파이썬

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

9461번: 파도반 수열

단계 : 동적 계획법 1

알고리즘 분류 : 수학, 다이나믹 프로그래밍

 

풀이:

나선 모양으로 놓여 있는 삼각형의 특정 몇번째 삼각형의 변의 길이가 몇인지 구하는 문제이다.

 

문제에서 첫 10개의 삼각형의 변의 길이는 [1, 1, 1, 2, 2, 3, 4, 5, 7, 9]라고 알려주었다.

이제 수열의 규칙성을 찾기 위해 다음 삼각형의 변의 길이를 구하면 되는데 문제에 그림이 있으니 그림을 살펴보자.

 

그림에는 12라는 길이의 삼각형이 마지막에 나와있다.변의 길이가 12인 11번째 삼각형은 이전 삼각형 두개와 맞닿아있다. 변의 길이가 9인 10번째 삼각형과 변의 길이가 3인 6번째 삼각형과 맞닿아있다.

또 그림을 살펴볼 경우 다음 삼각형은 12와 4가 합쳐진 16이 한 변의 길이인 삼각형이라는 것을 알 수 있으며 이 역시 12번째 삼각형이 11번째 삼각형(한 변의 길이 12)과 7번째 삼각형(한 변의 길이 5)가 맞닿아 있는 삼각형이라는 사실을 알 수 있다.

 

그렇기 때문에 우리가 구해야 할 N번째 삼각형의 경우 N-1 번째 삼각형과 N-5번째 삼각형의 변의 길이를 합친 값을 한 변의 길이로 가진다. 해당 점화식을 이용하여 문제에서 주어진 N의 범위인 100까지 처음에 구했다.

 

코드

import sys

info = [1, 1, 1, 2, 2, 3, 4, 5, 7, 9]

for i in range(len(info), 101):
    info.append(info[i - 1] + info[i - 5])

t = int(sys.stdin.readline())

for i in range(t):
    n = int(sys.stdin.readline())
    print(info[n - 1])