파도반 수열[백준 9461] - python

 

 

import sys 
input = sys.stdin.readline

def BOJ9461() :
  T = int(input())
  dp = [0] * 102
  dp[0] = 1
  dp[1] = 1
  dp[2] = 1
  for i in range(3, 102) :
    dp[i] = dp[i-3] + dp[i-2]


  for _ in range(T) :
    n = int(input())
    print(dp[n-1])

BOJ9461()

 

 

접근방법 

1. 점화식만 찾아내면 문제는 끝난다.(dp 문제들의 핵심인것 같다)

2. 문제에서 다행히 예시를 잘 보여주어서 점화식 찾기가 어렵지 않았다.

 

 

 

 

 

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

9461번: 파도반 수열