백준15988 - 1,2,3 더하기 3 (다이나믹 프로그래밍) JS

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

해당 문제는 DP, 즉 다이나믹 프로그래밍을 통해 해결해야 하는 문제다. 

 

다이나믹 프로그래밍이란, 상대적으로 복잡하고 큰 연산을 통해 해결해야 할 문제를

작은 단위로 쪼개어 해결함으로써 중복 계산을 피하며 최적화된 결괏값을 구하는 방식을 의미한다.

그리고 이때, 중복 계산을 피하기 위해 작은 단위의 계산을 저장해두는데 이때 이를 메모라이징이라 한다.

 

1, 1, 2, 3, 5, 8, 13... 과 같이 바로 뒤에 있는 수와 2번째로 뒤에 있는 수를 더해 만들어지는 피보나치 수열의 경우

다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예로 불린다.

피보나치 수열을 만드는 로직은 다음과 같다.

function fibonacci(n) {
  const arr = [1,1] // 작은 문제들의 해결 결과는 한 번만 계산하고 저장 (메모라이징)
  
  for(let i = 0 ; i < n ; i++) // 큰 문제를 작은 문제로 나눌 수 있어야 하며
    arr.push(arr.at(-2) + arr.at(-1)) // 작은 문제들의 해결 방법은 모두 동일해야 하고
  
  console.log(arr) // [ 1, 1, 2, 3, 5, 8 ]
}

fibonacci(4)

 

다이나믹 프로그래밍으로 문제를 해결하기 위해서는, 

해당 문제가 어떤 규칙을 가지고 있는지 파악하고 이를 작은 단위의 문제로 쪼개 해결하기 위한 '점화식'을 잘 수립하는 것이 중요하다.

 

하지만 위 문제에서는 점화식까지 어렵게 생각할 필요가 없는데,

4를 만드는 방법은 7가지라며 이미 문제 내에서 힌트를 주고 있기 때문이다.

 

1을 만드는 방법은 [1]로 한 가지.

2를 만드는 방법은 [1,1], [2]로 두 가지.

3을 만드는 방법은 [1,1,1], [1,2], [2,1], [3] 으로 네 가지.

4를 만드는 방법은 문제에서 제시되었듯 일곱 가지가 되는데,

이때 이는 1, 2, 3을 만드는 방법의 가짓수를 모두 합한 것과 같게 됨으로 

아래와 같은 점화식을 수립할 수 있게 된다.

f(n) = f(n-1) + f(n-2) + f(n-3)

 

이를 활용하여 풀이한 소스 코드는 다음과 같다.

onst fs = require('fs')
const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt")
  .toString().trim().split('\n')

input.shift()

function solution(data) {
  // 입력값 중 가장 큰 값을 기준으로 메모라이징을 만들어주면
  // 그 다른 입력값들도 재사용할 수 있게 된다
  const max = Math.max(...data)
  const dp = Array.from({length : max},()=> 0)
  dp[1] = 1
  dp[2] = 2
  dp[3] = 4

  for(let i = 4 ; i <= max ; i ++) {
    dp[i] = (dp[i-1] + dp[i-2] + dp[i-3])%1000000009
  }

  const result = data.map((el)=> dp[el])
  console.log(result.join('\n'))
}

solution(input)