#62. 백준 2839번 문제 풀이: 설탕 배달 문제 원본 보기
설탕공장에서 설탕을 배달하고 있다. 사탕가게에 N킬로그램을 배달해야 한다. 봉지는 3킬로그램과 5킬로그램 봉지가 있다. N킬로그램을 배달할 때, 가장 적은 수의 봉지 수를 구하는 프로그램을 작성하시오. 입력: 첫줄에 배달할 총용량 N. (3 ≤ N ≤ 5000) 출력: 배달하는 데 필요한 최소의 봉지 개수 정확하게 N킬로그램이 되는 조합이 없으면 -1 출력.
입력/출력
--입력--
18
--출력--
4
--입력--
4
--출력--
-1
--입력--
6
--출력--
2
문제풀이+해설
가장 적은수의 봉지로 조합하려면, 큰 무게의 봉지를 최대한 많이 가져야가야 한다.
 N = 5 * n5 + 3 * n3; 

쉽게 계산하는 방법은 N 에서 3kg봉지(3)를 하나씩 늘려가면서 뺀값이 5로 나누어지면 그때 개수가 최대의 5kg 봉지와 최소의 3kg 봉지수가 된다.

1. N을 큰봉지(5)로 나누어 나머지가 0 이 되거나 N값이 0보다 작을 때까지 아래 과정을 반복한다. 
2. N = N - 3(3kg봉지)를 빼주고, 3kg봉지수(n3)를 +1 한다. 1번을 다시 확인한다.
3. 루프가 끝나고, N이 0보다 작으면 봉지조합이 없으므로 -1 출력.
4. N 값이 0이상이면 5로 나눈값(n5)이 5kg봉지수. 5kg봉지수(n5) + 3kg봉지수(n3) 값을 출력한다.
code sol.
#include <iostream>
using namespace std;

int main() {
  int N, n3;
  
  cin >> N; // 배달할 설탕량 N 값을 정수형으로 받는다.
  if(N % 5 == 0) { // 5kg 봉지로 나누어 떨어지면 5로 나눈값이 최소봉지 값
    cout << N / 5; // 최소봉지값 출력
  } else { // 5kg봉지수로 안떨어 지면  
    n3 = 0; // 3kg봉지수, 초기값 0개
    while(N >= 0) { // N 중량이 0이상이면 루프.
      n3 += 1; // 3kg 봉지를 하나씩 늘려가면서 계산
      N -= 3; // 3kg를 빼준다
      if(N % 5 == 0) break; // 남은 중량이 5kg로 나눈 나머지가 0이면 조합 완성
    }
    if(N < 0) cout << -1; // 3kg, 5kg 봉지 조합이 없음
    else cout << (N / 5) + n3;
    // 5kg봉지수 + 나머지를 3kg봉지로 나눈수 = 조합봉지갯수 출력
  }
  return 0;
}
© 코드솔 - CodeSol. All Rights Reserved.