[구름톤 챌린지] 통증 (2) (JS)

풀이 과정

1. 통증 수치를 A, B 중 큰 수로 나눈 몫부터 시작해서 0까지 감소하면서 반복
2. 남은 수를 작은 수로 나누어 떨어지면 두 몫의 합이 결과(반복문 탈출)
3. 반복문이 끝날 때까지 나누어 떨어지는 수가 없으면 -1 리턴

코드

const readline = require('readline');
let rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
let input = [];
rl.on('line', (line) => {
  input.push(line.trim());
  if (input.length === 2) {
    rl.close();
  }
});

rl.on('close', () => {
  const N = Number(input[0]);
  const nums = input[1].split(' ').map(Number);
  const [big, small] = [Math.max(...nums), Math.min(...nums)];
  let result = -1;
  for (let i = Math.trunc(N / big); i >= 0; --i) {
    const rest = N - big * i;
    if (rest % small === 0) {
      result = i + rest / small;
      break;
    }
  }
  console.log(result);
  process.exit();
});

🦾

이전 통증 문제가 변형되었다고 하고, 동적 프로그래밍이 뭔지 몰라서 긴장했는데 어려운 문제는 아니었다. 동적 프로그래밍(DP)이란 큰 문제를 작은 문제로 나누어 푸는 방식이라고 한다. 일단 큰 수로 나누어보고 그 결과를 다시 작은 수로 나누어 보고 하는 방식이라 이 문제가 DP인가 보다.

08/29 해설 참조 후 추가
DP를 완전히 잘못 이해했던 것 같다 ㅋㅋㅋ 나는 그리디 변형 느낌으로 문제를 푼 것 같고..? DP는 통증이 0일 때부터 결과를 차곡차곡 배열에 저장해두는 식이었다. 피보나치처럼

N = Number(input[0]);
const [A, B] = input[1].split(' ').map(Number);
let DP = Array(N + 1).fill(Infinity);
DP[0] = 0;
for (let i = 0; i <= N; i++) {
  if (i - A >= 0) {
    DP[i] = Math.min(DP[i], DP[i - A] + 1);
  }
  if (i - B >= 0) {
    DP[i] = Math.min(DP[i], DP[i - B] + 1);
  }
}

console.log(DP[N] !== Infinity ? DP[N] : -1);