[백준] 9461 | 파도반 수열 [파이썬/python]

문제

link: https://www.acmicpc.net/problem/9461

문제에서 제시한 그림과 같이 정삼각형이 추가될 때, n번째 정삼각형 변의 길이 P(n)을 찾는 문제이다.

 

접근

문제에서 삼각형은 나선에서 가장 긴 변에 추가된다.

P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9인데, 여기에서 P(n) = P(n-2)+P(n-3)인 것을 알 수 있다.

리스트에 미리 값을 저장한 후 알맞게 출력해주었다.

 

코드

import sys
input = sys.stdin.readline

P = [0, 1, 1, 1] + [0] * 97

for i in range(4, 101):
    P[i] = P[i-3] + P[i-2]
    
for _ in range(int(input())):
    print(P[int(input())])