백준 9461 파도반수열(파이썬)

문제.

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

풀이.

P(1) 부터 P(10)까지의 수열을 보면 1, 1, 1, 2, 2, 3, 4, 5, 7, 9로 이루어져있다.

P(6)부터는 값의 구성이

Fn = F(n-1) + F(n-5)로 값이된다.

즉 DP를 이용해서 값을 저장하여 소스를 작성하면 된다.

 

소스코드.

n = [0] * 101 # 배열 생성
n[0:5] = [1, 1, 1, 2, 2] # 0~5까지의 값 저장하기

# 배열에 미리 값 저장
for i in range(5, len(n)):
    n[i] = n[i-1] + n[i-5]
    
tc = int(input())
for i in range(tc):
    number = int(input())
    print(n[number-1])