[백준/파이썬] 9461번 파도반 수열

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

9461번: 파도반 수열

dp문제는 왜인지 항상 블로그에 글을 쓰고 싶게 만든다.

처음 이 문제를 보면, 점화식을 만드는 규칙이 한 눈에 보이지 않아 무척 당황스러울 것이다.

하지만 연습장 하나 꺼내서 차근차근 손으로 계산하다보면 어떤 규칙이 눈에 띌 것이다 !

 

그 규칙은 바로 삼각형이 정삼각형, 역삼각형 꼴을 반복하는 것이고,

n번째 삼각형의 변의 길이 = 바로 직전의 삼각형의 변의 길이 + 직전 삼각형을 만드는데 쓰였던 삼각형 중 작은 것의 변의 길이이다!

직전의 삼각형을 만드는데 쓰였던 삼각형 중 작은 것은 현재 위치 기준으로 5번째 전의 삼각형이므로, 점화식은 아래 코드와 같다.

 

그러나 1번째 ~ 5번째 삼각형까지는 이 규칙 밖에 있으므로 6번째부터 구하면 될 것 같다.

import sys
#sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def get_dp():
  dp[1],dp[2],dp[3],dp[4],dp[5] = 1,1,1,2,2
  
  for i in range(6,101):
    dp[i] = dp[i-1] + dp[i-5]
    
if __name__ == "__main__":
  t = int(input())
  dp = [0 for i in range(101)]
  get_dp()
  for _ in range(t):
    print(dp[int(input())])