[2839] 설탕 배달

 

문제

 

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

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

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

 

 

 

문제 해석

 

설탕 요구량: N킬로그램

경우의 수: 3kg/ 5kg

문제 요구 사항: 적은 개수의 봉지로 배달하되 kg을 맞추지 못할 경우 -1을 출력

 

 

 

코드 및 풀이방식

 

처음 이 문제를 봤을 때 처음 생각했던 방법은 그냥 단순하게 if-else를 겹치는 거였는데 그렇게 생각했더니 case가 너무 많이 나왔다.

 

- case 1: 5로 나눠서 한번에 떨어지는 경우

- case 2: 5로 나눠서 떨어진 후 3으로 떨어지는 경우 / 떨어지지 않는 경우

- case 3: 처음부터 5로 나눠서 떨어지지 않는 경우 -> 3으로 나눠서 떨어지는 경우, 떨어지지 않는 경우

 

여기서 이 방법이 아니라는 것을 깨닫고 다른 방식을 시도 해 보았다.

 

 

이 문제에서 가장 핵심이 되는 것은 일단 전체 N의 값을 5로 나누는 것이다.

그 이후에 남는 값은 N=N-(5KG*봉지 개수)이다.

이 식을 보면 봉지개수에 따라 N의 수가 달라지는데, N의 수가 달라지면 3kg로 나누었을 때 나누어질지 안나누어질지 달라진다는 것이다.

 

 

<예시>

 

N=27일 때

5kg X 5개이면 3kg로 나누어 지지 않는다.

하지만 5kg X 0개이면 3kg X 9개로 가능하다.

 

여기서 언제 3kg로 나눴을 때 나머지가 0이 되는지 봉지의 개수를 줄여가면서 파악해야 한다는 것을 알 수 있다.ㅎ_ㅎ

그리고 봉지의 개수를 계속줄여서 0이 되었는데도 3kg로 나누어지지 않았다면 -1을 출력하면 된다.

 

 

<코드>

 

#include <iostream>
using namespace std;

 

int main(){
 int N = 0;
 int five = 0;
 int three = 0;

 

 // 무한 반복되게 코드 작성

 while (true){

  cout << "N을 입력하세요\n";
  cin >> N;

  
  if (N < 3 || N>5000) {

   cout << "범위에서 벗어나는 값 입니다.\n\n";
   continue; }

 

 // 먼저 5로 나눔(큰 수)

   five = N / 5;   

   while (five >= 0){
    N -= five * 5; // N에서 빠지는 값 (5kg봉지*개수)

   

 // 그게 3으로 떨어지면
     if (N % 3 == 0) {
     three = N / 3;
     cout << five + three << "\n";
     break; }

 

 // 안 떨어지면 5kg짜리 한 묶음씩 푼다.
    five--;
 }

 

 // 5kg짜리를 다 풀어도 못 맞추는 경우 -1 리턴
   if (five < 0) {
   cout << -1 << "\n"; }

}