백준 9461 - 파도반 수열 (Python3)

코드

T = int(input())

for _ in range(T):
    n = int(input())
    d = [0] * (n+1)
    
    if n == 1 or n == 2 or n == 3:
        print(1)
        continue
        
    if n == 4 or n == 5:
        print(2)
        continue
    
    d[1] = 1
    d[2] = 1
    d[3] = 1
    d[4] = 2
    d[5] = 2
    
    # 점화식
    for i in range(6, n+1):
        d[i] = d[i-1] + d[i-5]
        
    print(d[n])

문제 해설

동적 프로그래밍 참고

DP 문제이다. 다른 문제들과 마찬가지로 규칙을 파악한 후, 점화식만 세우면 간단하게 해결된다. 5번째 삼각형 (변의 길이가 3)일 때부터 규칙이 명확하게 보여 생각보다 간단하게 해결하였다.