[백준 9461번] 파도반 수열

def solution(n):
    dp = [0]*101
    dp[1], dp[2], dp[3], dp[4], dp[5] = 1, 1, 1, 2, 2

    if n<=5:
        return dp[n]

    for i in range(6,n+1):
        dp[i] = dp[i-1] + dp[i-5]
    
    return dp[n]


t = int(input())

result = []

for _ in range(t):
    n = int(input())
    result.append(solution(n))

for i in range(t):
    print(result[i])

이번 문제는 변의 길이가 1인 정삼각형 으로부터 시작하여 나선형으로 나선에서 가장 큰 변의 길이를 가진 정삼각형을 추가하는 방식으로 진행했을 때, n번째 삼각형의 변의 길이인 P(N)를 구하는 문제이다.

 

n번째 삼각형의 변의 길이에 대한 패턴을 찾기 위해 P(1)부터 P(10)까지 쭉 나열을 해보았더니, 다음과 같은 결과가 나왔다.

• P(1~5) = 1
• P(n) (n >=6) = P(n-1) + P(n-5)

위와 같은 점화식이 도출되고 나서, DP 알고리즘 중에서도 Top-Down 방식을 사용하여 문제를 해결할 수 있었다 :)

(재귀 함수를 이용한 탑-다운이 아니라, 반복문을 이용한 바텀-업 방식을 사용했다면 더 빠르게 풀이할 수 있었을 것이다.)