[백준 - Python] 9461. 파도반 수열 (DP)

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

9461번: 파도반 수열

 

코드

T = int(input())

for _ in range(T):
    N = int(input())
    dp = [0] * (N+1)
    for i in range(1, N+1):
        if i == 1 or i == 2 or i == 3:
            dp[i] = 1
        elif i == 4 or i == 5:
            dp[i] = 2
        elif i == 6:
            dp[i] = 3
        elif i == 7:
            dp[i] = 4
        elif i == 8:
            dp[i] = 5
        else:
            dp[i] = dp[i-1] + dp[i-5]
    print(dp[N])

 

처음 정삼각형부터 이어서 붙는 삼각형들을 눈으로 따라가보면서

어떤 규칙이 있을까 생각을 해보았다.

 

정삼각형이 시계방향으로 돌면서 나선 형태로 이어 붙는데

변의 길이가 5인 정삼각형부터는

첫번째 정삼각형(1)과 마지막 정삼각형(4)의 두 변의 길이를

합친 길이만큼의 정삼각형이 붙는 것을 확인할 수 있다.

 

따라서 dp[i] = dp[i-1] + dp[i-5] 이라는 점화식을 도출할 수 있었다.