[Java] baekjoon_2839 : 설탕 배달

수학, 다이나믹 프로그래밍, 그리디 알고리즘

설탕 배달 : Silver4

https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

 

 

풀이

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int bag5 = N / 5;
        int bag3 = 0;
        int r = 0;

        while (bag5 >= 0) {
          if (bag5 > 0) {
            r = N - bag5 * 5;
          } else {
            r = N;
          }

          bag3 = r / 3;
          r %= 3;

          if (r == 0) {
            bw.write(String.valueOf(bag5 + bag3));
            break;
          }
          bag5--;
        }

        if (r != 0) {
          bw.write("-1");
        }

        bw.newLine();
        bw.flush();
        bw.close();
    }
}

 

ㄴ N을 5kg짜리 봉지로 최대한 나눠보고, 남은 나머지를 r에 저장한다.
ㄴ 남은 나머지 r을 3kg짜리 봉지로 나눠보고, 남은 나머지를 다시 r에 저장한다.
ㄴ 만약 r이 0이면, 5kg짜리와 3kg짜리 봉지를 조합하여 N을 나눌 수 있으므로, 봉지의 개수를 출력하고 종료한다.
ㄴ r이 0이 아니라면, 5kg짜리 봉지의 개수를 1 감소시키고 다시 반복한다.
ㄴ 모든 반복이 끝나도 r이 0이 아니라면, 조합으로 N을 나눌 수 없는 경우이므로 -1을 출력한다.

 

---

 

 

문제점 : 처음에는 5kg 짜리로 나눈 뒤 3kg 짜리로 또 나눠서 나머지를 결정하도록만 했는데 N이 6일 경우 2가 출력되어야 하지만 -1이 출력되었다.

해결 방법 : 코드를 처음부터 다시 생각해서 작성하도록 했다. 5kg 짜리로 최대한 나눈 뒤 남은 나머지에 대해서 다시 3kg 짜리로 나눈 뒤 남은 나머지를 r에 저장하도록 했다. 여기서 r이 0이면 5kg 짜리와 3kg 짜리 봉지를 조합하여 N을 나눌 수 있으므로 두 봉지의 각 개수를 합하여 출력하도록 했다. r이 0이 아니라면, 5kg 짜리를 1개 줄인 뒤 다시 반복시켰다. 모든 반복이 끝나도 r이 0이 되지 않으면 -1을 출력하도록 했다.

깨달은 바 : 테스트 케이스에서 계속 옳은 출력이 발생하지 않는다면 코드를 다시 생각해서 작성해보는 것이 도움이 되는 것 같다.