백준19947 - 투자의 귀재 배주형 (DP) JS

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

 

문제는 초기 금액과 투자 기간과 1 / 3 / 5년의 기한마다 얻을 수 있는 이윤이 주어질 때,

주어진 투자 기간동안 최대로 얻을 수 있는 이윤을 구하는 문제다.

 

각 년차마다 얻을 수 있는 최대 이익을 기록하고, 이를 활용하여 다음 연산에 활용할 수 있도록

다이나믹 프로그래밍(DP) 알고리즘 기법을 활용하여 문제를 해결하였다.

 

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

function solution(data) {
  const [h, y] = data.split(' ').map(Number)
  
  const dp = Array.from({length : y + 1}, ()=> 0)
  dp[0] = h
  
  for(let i = 1 ; i <= y ; i ++) {
    // 이떄 ~~연산자는 Math.floor와 같은 역할을 한다
    dp[i] = ~~(dp[i - 1] * 1.05)
    // 현재연도가 3년 이상일 경우는, 3년 전 금액으로 3년 기한의 투자가 가능하기에
    // 아래와 같이 두 수 중 더 큰 수를 기록하며 진행한다
    if(i >= 3) dp[i] = ~~Math.max(dp[i], dp[i-3] * 1.2)
    if(i >= 5) dp[i] = ~~Math.max(dp[i], dp[i-5] * 1.35)
  }

  console.log(dp[y])
}

solution(input)