[BOJ] 9461 파도반 수열

문제

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

문제분석

종이와 펜을 들고, 규칙을 찾아보자.

이전 값들이 영향을 주네?

알고리즘 전략 선택

재귀냐 DP냐

• 재귀 -> 탑다운방식
• DP -> O(n) 만큼의 시간이 걸린다 ->상향식

시간복잡도상 DP를 선택하는 것이 유리해보인다.
그러면 DP와 단순 재귀를 판가름하는 기준은 무엇일까?

느낀점

고등학교 학창시절 수열문제를 풀이할 때, 몇 항까지 가야 비로소 규칙이 생기는 유형의 문제들이 있었다. 그런 유형을 당시 내가 듣던 인강 선생님은 노가다 수열이라고 불렀었는데, 오늘 푼 문제가 딱 이런 유형이었다.

성공한 풀이

const input = require('fs').readFileSync(0).toString().trim().split('\n').map(Number)

let answer = ''

const solution = (n) => {
  const arr = [0, 1, 1, 1, 2, 2, 3]
  for (let i = 7; i < n + 1; i++) {
    arr.push(arr[i - 1] + arr[i - 5])
  }
  return arr[n]
}

input.forEach((n, i) => {
  if (i === 0) return
  answer += solution(n) + '\n'
})

console.log(answer)