[알고리즘]백준 2839번: 설탕 배달 W_node.js

문제

2839번: 설탕 배달

풀이

const readFileSyncAddress = '/dev/stdin';

const fs = require('fs');
let [input] = fs
  .readFileSync(readFileSyncAddress)
  .toString()
  .trim()
  .replaceAll(/\r/g, '')
  .split(/\n/g)
  .map((v) => +v);

const solution = function (n) {
  let x = 1;
  let y = 1;
  while (5 * y < n) {
    y++;
  }
  if (5 * y === n) return y;
  while (y >= 0) {
    if (3 * x + 5 * y === n) return x + y;
    y--;
    if (3 * x + 5 * y === n) return x + y;
    x++;
  }
  return -1;
};

console.log(solution(input));

3x + 5y = N 일 때, x + y의 최솟값을 찾는 방식으로 접근했다.

먼저 x와 y 값은 1에서 출발하고, 최솟값을 만들기 위해 큰 숫자에 곱해지는 y의 최댓값을 while 문을 사용해서 구했다. 

그 뒤 5y가 n인 경우 가장 최솟값인 y를 리턴한다.

그렇지 않을 경우, y가 0 혹은 0이하가 될 때까지 3x + 5y 비교 > y 값 감소 > 비교 > x값 증가 의 과정을 거쳐 최소값이 되는 지점을 찾는다.

어떤 경우에도 n이 될 수 없을 때 -1을 리턴한다.

다른 답안

const readFileSyncAddress = '/dev/stdin';

const solution = function (n) {
  let cnt = 0;

  while (true) {
    if (n % 5 === 0) {
      return n / 5 + cnt;
    } else if (n <= 0) {
      return -1;
    }
    n -= 3;
    cnt++;
  }
};

console.log(solution(input));

위 답안은 구글링을 통해 참고한 다른 답안이다.

먼저 n 이 5로 나누어 떨어질 때, n / 5와 cnt를 리턴한다. n이 0 이하일 경우 -1을 리턴한다.

n에서 3을 빼고, 카운트를 올린 후, 위로 올라가 과정을 반복한다. 

내 답안에서 x를 증가하고 비교하고, y를 감소하고 다시 비교한 과정을 나누어 떨어졌을 때의 나눈 값(5짜리 설탕봉지) + cnt (3짜리 설탕봉지) 로 더 간략하게 비교할 수 있다.