백준<2839번> 설탕 배달

휜·2025년 9월 7일

Algorithm

목록 보기

3/7

문제

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

출력

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

예제 입력

입력값 => 출력값
18 => 4
4 => -1
6 => 2
9 => 3
11 => 3

문제 접근

5와 3으로 나눈다.
5를 최대로 넣고, 나머지를 3으로 채운다. (5는 많이, 3은 적게)
5로 나눈 몫이 3보다 작아질 때 까지 반복한다. (5로 나눈 몫이 3보다 작아질 때 까지 반복)
5로 안 나눠지면 3으로 나눠지는지 다시 검증한다
3으로도 나누어지지 않으면 5kg 봉지를 1개 줄인다. 3kg 봉지는 다시 리셋
(5)와 (7)을 계속 반복했음에도 불구하고 나머지가 0이 되지 않으면 -1을 반환

➡️ 그리디 알고리즘

그리디 알고리즘?
💡 최대한 큰 것을 먼저 시도하고, 큰 것이 더이상 반복되지 않게된다면 하나를 줄이고 그 다음 큰 것을 하나 추가하여 최적의 비율 or 효율을 찾는 알고리즘

정답 전, 오답

최초 작성 코드는 아래와 같다.

function solution(N) {
  let fiveKgBag = 0;
  let threeKgBag = 0;

  const remainderOfFiveBag = Math.floor(N / 5);

  // 5kg 봉지가 0임에도 불구하고 나머지가 3kg 봉지로 채워지지 않는다면 -1 반환
  for (let i = remainderOfFiveBag; i >= 0; i--) {
    console.log({ i });
    fiveKgBag = i;

    console.log(fiveKgBag * 5);
    console.log(threeKgBag * 3);
    if (fiveKgBag * 5 + threeKgBag * 3 === N) {
      console.log("최종 반환값: ", fiveKgBag + threeKgBag);
      return fiveKgBag + threeKgBag;
    } else {
      threeKgBag++;
    }
  }

  console.log("예외케이스 최종 반환값: ", -1);
  return -1;
}

solution(11); // 4

해당 코드의 문제는 threeKgBag 변수 스코프 관리와 모든 조합을 시도하지 않았던 것이다.

이 코드에서 5kg는 많이 넣을 수 있지만, 3kg는 얼마나 넣을 수 있는지 고려되지 못하고 있다.

아래 정답에서 변수 스코프 및 모든 조합 시도를 하도록 코드를 수정하였다.

정답

function solution(N) {
  let fiveKgBag = Math.floor(N / 5); // 최대한 5kg 사용
  let threeKgBag = 0; // 3kg는 0부터

  while (fiveKgBag >= 0) {
    const total = fiveKgBag * 5 + threeKgBag * 3;

    console.log({ fiveKgBag });
    console.log({ threeKgBag });
    console.log("-----------------------");

    if (total === N) {
      console.log("최종 반환값: ", fiveKgBag + threeKgBag);
      return fiveKgBag + threeKgBag;
    } else if (total < N) {
      threeKgBag++; // 부족하면 3kg 추가
    } else {
      fiveKgBag--; // 초과하면 5kg 줄이고
      threeKgBag = 0; // 3kg 리셋, 3kg가 얼마나 들어갈 수 있는지 확인하기 위함
    }
  }

  console.log("예외케이스 최종 반환값: ", -1);
  return -1;
}

solution(7); // 4