Baekjoon 14501번 퇴사

문제

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

걸린 시간

- 실패

풀이

JavaScript

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input';
const stdin = fs.readFileSync(filePath).toString().trim().split('\n').map(s => s.trim());
const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

let n = parseInt(input());

const a = []
for(let i = 0; i < n; i++){
  a.push(input().split(' ').map(Number));
}

const solve = (i) => {
  // 기저 사례
  if(i >= n) return 0;
  // 재귀 호출
  let ret = 0;
  const [t, p] = a[i];
  if(i+t <= n) ret = Math.max(ret, solve(i+t)+p); // i 는 이전 상담이 완료된 후 다음일
  ret = Math.max(ret, solve(i+1));
  return ret;
}

console.log(solve(0));

그리디로 접근하다 틀린 문제.

1일부터 차례대로 상담을 할지 말지 모든 경우를 조사해야 한다.