백준 2839번 - 설탕 배달

문제

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

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

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

입력

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

18

출력

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

4

 

내 코드

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int divide = n / 5;
    int result = 0;
    while (divide >= 0) {
      if ((n - divide * 5) % 3 == 0) {
        result += divide + (n - divide * 5) / 3;
        break;
      } else {
        divide--;
      }
    }
    if (result != 0) {
      System.out.println(result);
    } else {
      System.out.println(-1);
    }
  }
}

 

봉지는 5킬로그램과 3킬로그램 밖에 없다. 봉지를 최대한 적게 가져가고 싶다고 해서 5킬로그램으로만 나눠 담아가면 1킬로그램, 2킬로그램, 혹은 4킬로그램 이렇게 남아버릴 수도 있다.

 

바보가 일단 5킬로그램의 봉지로만 나눠담는다고 가정하자. 남은게 없거나 3킬로그램이 딱 남는다면 좋겠지만 그렇지 않을 수 있다. 그렇다면 바보는 일단 5킬로그램 봉지 하나만 다시 풀어서 남은것과 합치고 이것을 3킬로그램으로 나눠 담을 수 있는지 생각해볼 것이다. (쓰고보니 꽤 똑똑한 것 같다.) 만약 그 합계가 3킬로그램으로 정확히 나눠진다면 오케이. 3킬로그램 봉지로 나눠서 들고갈 것이다. 그러나 만약 그래도 합계가 3킬로그램으로 정확히 나눠 떨어지지 않는다면 아까 묶어둔 5킬로그램 봉지를 하나 더 풀 것이다. 이러한 방식으로 5킬로그램을 하나씩 풀어서 확인해보다가 5킬로그램 봉지는 하나도 없고, 3킬로그램 봉지만으로 나눠서 가져가게 될 수도 있고, 결국 3킬로그램으로도 나눠떨어지지 않아서 못 가져가게 되는 결과도 생길 수 있다.

 

이러한 과정을 그대로 코드로 옮긴다. 일단 설탕 그램수(n)를 5로 나눈 몫(divide)을 저장한다. 이것이 5킬로그램에 될 수 있는 대로 담은 최초의 경우가 된다. n에서 divide * 5를 빼준 나머지가 3으로 나눠 떨어지면(설탕이 하나도 안남았을 때에도 결과는 3으로 나눈 나머지는 0일 것이다.)) result에 5킬로그램 봉지 수(divide)와 3킬로그램 봉지 수 ((n - divide * 5) / 3)를 더한 결과를 저장하고 반복문을 빠져나온다. 만약 나눠 떨어지지 않으면 5킬로그램 봉지 하나를 풀고 (divide--) 다시 나머지들이 3으로 나눠떨어지는 지 확인한다. 이것을 5킬로그램 봉지가 남아나지 않을 때까지(divide >= 0) 반복한다. 반복문이 끝나면 result를 답안으로 출력한다. 만약 그렇게 반복문을 돌리고도 3으로 나눠떨어지지않았다면 result는 여전히 0일 것이므로 그 조건에만 -1을 출력한다.