[백준] 9461 파도반 수열 파이썬 풀이 (동적 계획법)

백준

 

문제

• 파도반 수열은 1 1 1 2 2 3 4 5 7 9 12 ... 이다
• 4번째 수인 2부터 보면 2번째 수와 1번째 수를 더한 값이다.
• 6번째 수인 3은 4번째 수인 2와 3번째 수인 1을 더한 값이다.
• n번째 수는 n-2번째 수와 n-3번째 수를 더 한 값이다.

 

풀이

• N은 100까지밖에 안되므로 미리 구해놓자
• dp 배열을 100인덱스까지 만들어놓고 1 2 3 번째는 1로 초기화.
• 4번째 부터 위에서 말한 규칙을 적용하여 dp배열을 미리 만들어 놓음

 

코드

num = int(input())

dp = [0 for i in range(101)]
dp[1] = 1
dp[2] = 1
dp[3] = 1

for i in range(4,101):
    dp[i] = dp[i-2] + dp[i-3]


for _ in range(num):
    test = int(input())
    print(dp[test])