[python/백준/DP] 9261: 파도반 수열

문제

풀이

1. 수열의 규칙 찾기

• 이 수열의 규칙은 아래와 같다.

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

  dp[1] = 1
  dp[2] = 1 
  dp[3] = 1 
  dp[4] = dp[1]+dp[2] = 2
  dp[5] = dp[2]+dp[3] = 2 
  dp[6] = dp[3]+dp[4] = 3 
  dp[7] = dp[4]+dp[5] = 4 
  ...

2. 점화식
   dp[n] = dp[n-2] + dp[n-3] (단, n은 3보다 큰 숫자)

코드

T = int(input())

dp = [1]*101

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

for i in range(T):
    n = int(input())
    print(dp[n])