알고리즘 풀이/백준

백준 9461번 : 파도반 수열 (Python)

heheh 2021. 2. 6. 18:53

문제 : www.acmicpc.net/problem/9461

 

9461번: 파도반 수열

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

www.acmicpc.net

 

풀이

dp에 P(n)의 값을 저장한다.

n이 5 이상이 되면 해당 값은 P(n-5)+P(n-1)의 값을 가진다.

 

t = int(input())

dp = [0, 1, 1, 1, 2]
for _ in range(t):
    n = int(input())
    if n > len(dp)-1:
      for i in range(len(dp),n+1):
          dp.append(dp[i-5]+dp[i-1])

    print(dp[n])