9461. 파도반 수열

✨ Daily CodingTest  시간에 푼 문제

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

 

✔ 유형 : DP

✔ 문제 풀이: 규칙을 찾아 수가 작은 경우부터 결과 값을 배열에 채워나감.

 

이번 문제 같은 경우에는 초기값이 많았다.

처음 변이 1인 삼각형에서 시작해서 변이 1인 삼각형과 2인삼각형이 일직선상에 놓이기 전까지는 일반화를 할 수가 없다.

따라서, 

DP[0] = 0

DP[1] = 1

DP[2] = 1

DP[3] = 1

DP[4] = 2

DP[5] = 2

 

N = 5일 때까지는 값을 정해줘야 한다.

 

그 이후에는 다음과 같은 점화식을 따른다.

 

DP[N] = DP[N - 5] + DP[N - 1]

 

점화식을 이용해 배열을 채워 나가면 N일 때의 값을 구할 수 있다.

 

 

코드

import sys
input = sys.stdin.readline

N = int(input())

def wave(N: int):
    DP = [0 for _ in range(N+1)]
    setting = [1,1,1,2,2]
    
    for i in range(1,N+1):
        if i > 5 :
            break
        
        DP[i] = setting[i-1]

    if N >= 6:
        for j in range(6, N+1):
            DP[j] = DP[j-5]+DP[j-1]
        
        
    print(DP[N])
    
for _ in range(N):
    wave(int(input()))