[백준 14501] 퇴사

문제

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

아이디어

동적 프로그래밍을 이용해 각 회의를 진행할 때의 보수를 기록하고 이후에 다른 회의를 진행할 때에도 기록했던 보수를 활용하면서 새로운 회의를 진행하는게 최대 수익이 나오는지, 아니면 기존에 계산했던 회의를 진행하는게 최대 수익이 나오는지를 알아보면 된다.
arr를 '상담을 완료하는데 걸리는 시간' 과 '상담을 했을 때 받을 수 있는 금액' 이 담겨있는 배열이고
earning을 'i번째 상담의 보수를 계산하기까지의 최대 보수' 가 담겨있는 배열이라고 정의한다.

첫 번째 라운드

첫 번째 회의를 진행하면 4일차부터 다른 회의를 진행할 수 있다.

두 번째 라운드

두 번째 회의를 진행하면 7일차부터 다른 회의를 진행할 수 있다.

세 번째 라운드

세 번째 회의를 진행하면 4일차부터 다른 회의를 진행할 수 있다.
그러나 회의를 진행했을 때 받는 금액이 기존의 계산보다 크지 않기 때문에 earning[4] 이후의 값에 주는 영향이 없다.
세 번째 회의의 보수는 10이지만, 바로 이전 회의를 진행하면 20을 받을 수 있기 때문에 20을 기록한다.

네 번째 라운드

네 번째 회의의 보수는 20이고 첫 번째 회의 이후에 네 번째 회의를 진행한다면 30의 보수를 받을 수 있다.
또한 네 번째 회의를 진행하면 5일차부터 다른 회의를 진행할 수 있다.

다섯 번째 라운드

다섯 번째 회의의 보수는 15이고 네 번째 회의 이후에 다섯 번째 회의를 진행한다면 45의 보수를 받을 수 있다. 또한 다섯 번째 회의를 진행하면 7일차부터 다른 회의를 진행할 수 있다.

여섯 번째 라운드

다섯 번째 회의의 보수는 40이고 네 번째 회의 이후에 여섯 번째 회의를 진행한다면 75의 보수를 받을 수 있지만 네 번쨰 회의의 소요 시간은 4일이므로 퇴사일 전에 끝낼 수 없는 회의이다. 그러므로 진행할 수 없다.
그렇지만 바로 이전 다섯 번째 회의를 진행하면 45의 보수를 받을 수 있기 때문에 45를 기록한다.

일곱 번째 라운드

일곱 번째 회의의 소요 시간은 2일이므로 퇴사일 전에 끝낼 수 없는 회의이다.

이러한 과정을 통해 최대 수익은 45라는 사실을 알 수 있다.

각 회의마다 순회하며 아래를 반복한다.

1. 퇴사일 전에 끝나는 회의라면 현재 회의를 진행할 때 받을 보수를 earning에 기록한다.
2. 만약 현재 회의를 진행하지 말고 이전의 회의를 진행하는 것이 보수가 더 크다면 이전의 회의를 선택한다.

해결 과정

문제에서 제공하는 테스트 케이스는 통과하였으나 검사에 계속 실패해서 문제점을 생각하는데에 시간이 더 걸렸다.
모든 회의의 소요 시간이 퇴사일보다 오래 걸려서 아예 보수를 받지 못해서 정답이 0이 나와야 하는 경우가 있었고
i-1번째 회의의 기록된 보수가 i번째 회의를 진행했을 때의 보수보다 크다면 그냥 i-1번째 회의의 보수를 반영해야 한다는 경우가 있었다.

소스코드

// 입력 처리
const INPUT_NAME = 'i4.txt';
const filePath = process.platform === 'linux' ? '/dev/stdin' : `./${__dirname.split('\\').pop()}/${INPUT_NAME}`;
const input = require('fs').readFileSync(filePath).toString().trim().split('\n').map(item => item.trim());
const n = Number(input[0]);
const earning = Array.from({ length: n }, () => 0);
const arr = [];
for (let i = 1; i <= n; i++) {
  arr.push(input[i].split(' ').map(e => Number(e)));
}

// idx번째 회의를 했을 때 받는 금액 정보를 업데이트한다.
function update(idx) {
  const newEarn = arr[idx][1] + earning[idx];
  const startIdx = idx + arr[idx][0];

  // 만약 해당 회의를 기한에 맞출 수 없다면 계산하지 않는다.
  if (startIdx > n) return;

  // 해당 회의의 보수를 기록한다.
  earning[idx] = Math.max(earning[idx], newEarn);

  // 다른 회의가 가능한 시점에 더 높은 보수를 기록한다.
  for (let i = startIdx; i < n; i++) {
    earning[i] = Math.max(earning[i], newEarn);
  }
}


// 문제
function solution() {

  // 첫번째 회의
  update(0);
  
  // 두번째 ~ 마지막 회의
  for (let i = 1; i < n; i++) {
    update(i);
    // 만약 i번째 회의보다 그냥 i-1번째 회의를 하는 것이 더 보수가 크다면 i-1번째 회의의 보수를 받는다.
    earning[i] = Math.max(earning[i], earning[i - 1]);
  }

  console.log(earning[n - 1]);
}

// 실행
solution();