백준14501 - 퇴사(DP) JS

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

문제는 '퇴사 전'까지 가장 많은 수익을 얻는 경우의 수익을 구하는 문제다.

상담마다 필요한 '기간'이 주어지기 때문에 모든 상담을 진행할 수 없는데, 

이 때 모든 경우의 수를 직접 구할 수 없으므로 DP를 통해 해결한다.

 

위 문제에서 주어진 예시로 설명을 하자면, 접근 방식은 다음과 같다.

1일차에 상담을 진행했다고 한다면(소요기간 3일 / 수익 10), 

소요기간이 3일이기 때문에 2-3일은 다른 사람과의 상담이 불가능하고,

나머지 일자에는 1일차에 상담을 진행한 경우의 아래와 같이 수익을 남게 한다.

(4,5,6,7일차에 상담을 한다면, 1일차의 수익까지 가져갈 수 있기 때문)

1일	2일	3일	4일	5일	6일	7일
10	0(상담 X)	0(상담 X)	10	10	10	10

 

여기서 2일차에 상담을 진행했다고 한다면(소요기간 5일 / 수익 20), 아래와 같은 표가 그려진다.

1일	2일	3일	4일	5일	6일	7일
10(1일차 수익)	20(2일차 수익)	0(상담 X)	10(상담 X)	10(상담 X)	10(상담 X)	20 (2일차 수익)

 

여기서 중요하게 보아야 할 것은, 상담을 못하는 기간 동안에는 기록한 수익을 그대로 유지시키고,

7일차에는 1일 상담으로 얻은 수익(10)보다, 2일 상담으로 얻은 수익(20)이 더 크기 때문에 더 큰값으로 수정한다.

 

이를 코드로 옮기면 다음과 같다.

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

function solution(data) {
  // 퇴사까지의 날짜
  const N = +data.shift()
  const dp = Array.from({length : N}, ()=> 0)

  data.forEach((el, idx)=> {
    const [days,price] = el.split(' ').map(Number)
    
    // 현재 일자와 소요 일자가 퇴사일을 넘지 않는 경우만 계산
    if(N >= idx + days) {
      // 현재 일자에 상담하는 경우 기록
      dp[idx] += price

      // 상담이 불가능한 날짜 이후의 날짜부터 더 큰값으로 기록 수정
      for(let j = idx + days ; j < N ; j ++) 
        dp[j] = Math.max(dp[j], dp[idx])
    }
  })

  console.log(Math.max(...dp))
}

solution(input)