[백준9461] / 파도반 수열 - DP

 

백준9461

 

푼 날짜 : 2024.10.18

푼 문제 : [9461] / 파도반 수열

사용한 언어 : python

알고리즘 : DP

 

 

점화식 :

dp[i] = dp[i-3]+dp[i-2]

 

생각보다 쉬웠던 점화식 찾기!

 

P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9

 

 

라고 문제에 주어졌기 때문에 확인해보면 3번째 전 숫자와 2번째 전 숫자를 더하면 현재 숫자가 나온다.

 

 

1, 1, 1, 2, 2, 3, 4, 5, 7, 9

1, 1, 1, 2, 2, 3, 4, 5, 7, 9

1, 1, 1, 2, 2, 3, 4, 5, 7, 9

1, 1, 1, 2, 2, 3, 4, 5, 7, 9

.

.

.

1, 1, 1, 2, 2, 3, 4, 5, 7, 9

 

 

이렇게 !!!

 

 

 

코드 :

T = int(input())

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

for _ in range(T):
    
    N = int(input())

    if N < 3:
        print(dp[N])
        continue # 아래 코드 실행하지 않기 위함

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

 

 

다이나믹 프로그래밍은 흥미로워라 ~~~~!!