문제

정량 N에 정확히 맞춰야만 움직이는 화물용 엘리베이터가 있습니다.
화물은 7kg, 3kg 두 가지이며 팔이 아픈 은후는 가장 적게 화물을 옮기고 싶습니다.

예를 들어 정량이 24kg이라면 3kg 8개를 옮기는 것보다는
7kg 3개, 3kg 1개 즉 4개로 더 적게 옮길 수 있습니다.

// 입력
정량 N이 입력됩니다.

// 출력
가장 적게 옮길 수 있는 횟수를 출력합니다.
만약 어떻게 해도 정량이 N이 되지 않는다면 -1을 출력합니다.

해결 방안

원래 문제는 화물의 중량이 7kg, 3kg으로 고정되어 있었지만, 화물의 중량을 임의의 자연수로 이뤄진 배열로 받아서 해결하는 방안을 고안했다.

우선, 성공적인 케이스를 하나 가정해서 시나리오를 작성해봤다.
정량 : 29kg, 화물 : [3, 5, 7, 9]인 성공 케이스

	9kg	7kg	5kg	3kg	총무게	남은 무게
1회차	3	0	0	0	27kg	2kg
2회차	2	1	0	1	28kg	1kg
3회차	2	0	2	0	28kg	1kg
4회차	2	0	1	2	29kg	0kg

화물을 최대한 적게 옮기기 위해선 가장 무거운 화물을 최대한 많이 옮겨야한다.

• 1회차: 9kg을 최대한 많이 3회 옮겨보지만 목표무게 29kg에서 2kg이 남아서 실패한다.
• 2회차: 9kg을 1회 줄인 뒤, 두번째로 무거운 화물인 7kg을 1회 옮기고 3kg을 1회 옮겨보지만 실패한다.
• 3회차: 7kg을 1회 줄인 뒤, 5kg을 최대한 많이 옮겨보지만 또다시 1kg이 남아서 실패한다.
• 4회차: 5kg을 1회 줄인 뒤, 3kg 2회로 남은 무게 0kg을 달성해 성공한다.

위 과정은 두 가지의 공정으로 나눌 수 있다.

• 화물들을 무거운 순으로 최대한 많이 옮겼을 때 각 화물 당 몇 회가 가능한 지 확인(check) 공정
• 실패했다면, 가장 가벼운 무게를 제외하고 그 다음으로 가벼우면서 0이 아닌 무게의 운반 횟수를 1회 줄이는 조정(adjust) 공정

이 두 가지의 공정을 성공할 때까지 반복하는 것이다.

이번에는 실패하는 케이스의 시나리오를 작성해본다.

정량 : 7kg, 화물 : [3, 5, 14]인 실패 케이스

	14kg	5kg	3kg	총무게	남은 무게
1회차	0	1	0	5kg	2kg
2회차	0	0	2	6kg	1kg

• 1회차: 5kg을 최대한 많이 1회 옮겨보지만 목표무게 7kg에서 2kg이 남아서 실패한다.
• 2회차: 5kg을 1회 줄인 뒤, 가장 가벼운 화물인 3kg을 2회 옮겨보지만 실패한다.

결국, -1을 반환해야 하는 경우는 가장 가벼운 무게만으로 최대한 운반했는데도 실패했을 때이다.

위 과정을 기반으로 아래와 같은 코드를 작성했다.

/**
 * 엘리베이터의 적재중량에 맞춰 화물을 옮기는 조건하에 가능한 최소 운반 횟수를 반환하는 함수
 * @param {number} N 엘리베이터가 움직일 수 있는 적재중량
 * @param {Array<number>} cargoWeights 화물들의 무게
 * @returns 최소 운반 횟수
 */
function countTheLeastMovement(N, cargoWeights) {
  // 정량 N을 계속 수정할 것이므로 새로운 변수에 할당
  let loadingWeight = N;
  // 확인을 시작할 위치를 0으로 초기화
  let from = 0;
  // 화물을 무거운 순으로 정렬하고 각 화물당 운반횟수를 0으로 초기화한다.
  const weights = cargoWeights
    .sort((a, b) => b - a)
    .map((weight) => [weight, 0]);

  // 총 운반횟수
  let count = 0;

  while (count === 0) {
    // 확인 과정을 거치고 남은 무게를 반환받는다.
    const remainingWeight = check(from, weights, loadingWeight);

    // 남은 무게가 0이라면 성공한 것이므로
    if (remainingWeight === 0) {
      // 각 화물당 운반횟수를 모두 더해서 count에 할당한다.
      count = weights.reduce((acc, weight) => acc + weight[1], 0);
    }

    // 확인 시작 위치와 화물들의 무게를 조정한다
    const { newFrom, newExceptedWeight } = adjust(from, weights);

    // 제외할 무게가 0이라면 정량이 되는 경우가 없다는 뜻이므로
    if (newExceptedWeight === 0) {
      // count에 -1을 할당한다.
      count = -1;
      // 0이 아니라면
    } else {
      // 새로 확인을 시작할 위치와 남은 무게를 설정한다.
      from = newFrom;
      loadingWeight = N - newExceptedWeight;
    }
  }

  return count;
}

/**
 * 화물들을 최대한 운반해보고 남은 무게를 반환하는 함수
 * @param {number} from 확인을 시작할 위치
 * @param {Array<number>} weights 화물들의 무게
 * @param {number} loadingWeight 적재중량 N
 * @returns 남은 무게
 */
function check(from, weights, loadingWeight) {
  // 화물들을 순회하면서
  for (let i = from; i < weights.length; i++) {
    // 화물의 무게가 정량보다 가벼우면
    if (weights[i][0] <= loadingWeight) {
      // 해당 무게로 가능항 운반횟수를 구해서
      let count = Math.floor(loadingWeight / weights[i][0]);
      // 화물의 운반횟수로 할당하고,
      weights[i][1] = count;
      // 운반한 총 무게를 정량에서 빼준다.
      loadingWeight -= weights[i][0] * count;
    }
  }

  // 순회를 마치고 남은 무게를 반환한다.
  return loadingWeight;
}

/**
 * 다음 회차의 확인을 시작할 위치와 무게를 조정하는 함수
 * @param {number} from 확인을 시작할 위치
 * @param {Array<number>} weights
 * @returns 새로 확인을 시작할 위치, 새로 확인을 시작할 때 제외할 무게
 */
function adjust(from, weights) {
  let exceptedWeight = 0;

  // 두번째로 가벼운 화물부터 순회를 해서
  for (let i = weights.length - 2; i >= 0; i--) {
    // 만약 화물의 운반횟수가 0이 아니라면
    if (weights[i][1] !== 0) {
      // 운반횟수를 1회 줄이고
      weights[i][1] -= 1;
      // 다음 순회시 제외해도 되는 무게를 구한 뒤,
      exceptedWeight = weights
        .slice(0, i + 1)
        .reduce((acc, weight) => acc + weight[0] * weight[1], 0);
      // 다음 회차에서 확인을 시작할 위치를 운반횟수를 줄인 화물로 설정하고,
      from = i + 1;
      // 순회를 종료한다.
      break;
    }
  }

  return { newFrom: from, newExceptedWeight: exceptedWeight };
}

const N = 29;
const cargoWeights = [9, 7, 5, 3];
const result = countTheLeastMovement(N, cargoWeights);
console.log("결과", result);