[ BOJ / 파이썬 ] 9461. 파도반 수열

dp 좋다.. 감이 잡히니까 확실히 내 타입 문제란 걸 알겠다.

원래도 규칙성 있는 걸 좋아해서 수열 문제 좋아했는데,

DP자체가 일반항 세우는거라 불규칙성 속에서 규칙 찾아내는 게 핵심이라 수열 문제가 많은 것이었다.

그래서 DP가 비교적 난이도가 쉬운 문제도 많이 분포하는 것이었다. 그러니까 DP문제는 사실상 DP테이블을 만드는 자체가 힘든게 아니라 DP테이블, 즉 메모제이션(탑다운 방식)을 차용할 생각만 떠올리면 되는것이고, 그 규칙을 찾아내느냐가 핵심인 경우가 많았다.

물론 내가 문제를 아직 많이 못 접해서 DP테이블을 어렵게 사용하는 걸 모르기 때문에 하는 얘기일 수도 있다. 어렵게 내려면 엄청 어려워질 수 있다고 한다. 뭐 이거야 계속 하다보면 늘겠지..

 

하여간 해당 문제는 이게 수열이라는걸 짚어내는게 중요했는데 도형 색에 집팍하느라 회전 방향을 순간 헷갈려서 초반에 약간 꼬였다.

불규칙 초기값이 단순한 문제처럼 1개, 2개가 아니라 5개가 된다는 것도 이 문제의 포인트였다. 항상 사고를 유연히 ~

 

점화식 찾은 뒤 풀이 자체는 쉬웠다. (근데 예외처리 이게 최선인가??)

tc = int(input())
for test_case in range(tc):
  n = int(input())
  dp = [0] * n
  dp[0] = 1
  if n > 1:
    dp[1] = 1
  if n > 2:
    dp[2] = 1
  if n > 3:
    dp[3] = 2
  if n > 4:
    dp[4] = 2
  if n > 4:
    for i in range(5, n):
      dp[i] = dp[i-1] + dp[i-5]
  print(dp[n-1])