[백준] [2839] 설탕 배달 (JAVA) (dp)

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

2839번: 설탕 배달

---

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

304208

112802

84822

36.726%

문제

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

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

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

입력

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

출력

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

---

※ JAVA 코드 (설탕 배달)

import java.io.*;
import java.util.*;

public class Main {
    public static boolean chk;

    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        System.out.println(dp(n));
    }
    public static int dp(int n)
    {
        int result = 0;

        while(n > 0) {
            // 5의 배수일때
            if(n % 5 == 0) {
                result += n / 5;
                chk = true;
                break;
            }

            if (n - 3 == 0) {
                result += 1;
                chk = true;
                break;
            }

            n -= 3;
            result += 1;
        }

        if(chk) {
            return result;
        } else {
            return -1;
        }
    }
}

---

※ 생각 정리 (설탕 배달)

1. dp 문제이해하기 - 작은 것에서 큰 것까지 만들어가는 과정

2. 큰 수를 만들기 위해 또는 큰 수에서 역으로 작은 것 까지의 최소를 구하기도 한다.

설탕 배달 문제를 풀기 위해 가장 중점으로 두어야하는 것은 5kg, 3kg 두가지 경우에서 만 선택을 해야하고 만약 가능하다면 최대한 5kg을 선택하는 것이 좋다.

그렇기 때문에 설탕의 무게가 5의 배수라면 무조건 5kg봉지에 담아가는 것이 좋다. 하지만 5의 배수가 아니라면 어쩔 수 없이 3키로씩을 빼주는 것이다. 이때 3의 배수로 나누지 않는다. 왜냐하면 최대한 5kg봉지를 사용해야하기 때문이다.

만약 계속해서 5의 배수가 나오지 않는다 하더라고 계속 해서 3을 빼서 5의 배수가 나올때까지 반복한다. 그 때 5의 배수가 나온다면 5로 나누어 그 몫을 더해주고 끝까지 3씩 빼나가다가 3보다 작고 5로도 나누어 떨어지지 않는 수가 나온다면 정확히 담을 수 없으므로 -1을 출력한다.

 

- 새벽코딩 -