백준 2839 Java - 설탕 배달
제목 : 설탕 배달
문제
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다.
상근이는 지금 사탕가게에 설탕을 정확하게 N 킬로그램을 배달해야 한다.
설탕공장에서 만드는 설탕은 봉지에 담겨져 있다.
봉지는 3 킬로그램 봉지와 5 킬로그램 봉지가 있다.
상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다.
예를 들어, 18 킬로그램 설탕을 배달해야 할 때, 3 킬로그램 봉지 6 개를 가져가도 되지만,
5 킬로그램 3 개 와 3 킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.
상근이가 설탕을 정확하게 N 킬로그램 배달해야 할 때,
봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N 이 주어진다. (3 <= N <= 5000)
출력
상근이가 배달하는 봉지의 최소 개수를 출력한다.
만약, 정확하게 N 킬로그램을 만들 수 없다면, -1 을 출력한다.
| 예제 입력 | 예제 출력 |
|---|---|
18 |
4 |
4 |
-1 |
6 |
2 |
9 |
3 |
11 |
3 |
이 문제는 실 생활에서의 "잔돈 거슬러주기" 문제보다는 조금 더 생각해야 할 문제이다.
실제로 이전 단계의 문제에서는 어떠한 값이던 매칭되는 값이 존재하여
매칭을 못하는 경우는 존재하지 않았다.
예를 들어, 950 원을 거슬러 주어야 한다고 하면,
500원 1개, 100원 4개, 50원 1개 거슬러 주면 될 것이다.
하지만, 이 문제는 3KG, 5KG 으로 설탕을 배달 해 주고 있다.
이 때 발생하는 문제는 2 가지 이다.
- 정확히 배달 해 주지 못할 무게가 존재한다. EX - 4 KG
- 매칭 할 수 있는 "모든 경우의 수" 중에서, 가장 적은 봉지를 사용하는 경우를 추출해야 한다는 것.
그런데, 실제로 이 문제가 실 생활 문제라고 생각 해 보자.
내가 만약에 설탕가게 사장인데, 봉지 자체의 값이 비싸 이를 절약하여 최소화 하고자 한다면,
이전에 설탕을 배달했을 때의 최소값을 기억하여 조합 할 것이라고 생각이 든다.
물론, 우리는 컴퓨터를 이용하기 때문에, 최소값을 구할 수 있다.
풀이 방식에 대한 견해
1 번째 풀이 방식 (Brute Force)
우리는 컴퓨터를 이용하여 굉장히 빠르게 계산하기 때문에,
배달해야 하는 설탕 봉지의 최소값을 3KG, 5KG 의 기준 중 하나로 구할 수 있다.
원하는 것 하나로 구하면 된다.
예를 들어, 단순히 내가 3KG 을 기준으로 세웠다면, (21 키로의 설탕을 배달한다 가정)
3KG x 0개일 때,5KG으로 정확히 나누어지는지, 그렇다면 몇 개가 필요한지 저장3KG x 1개일 때,5KG으로 정확히 나누어지는지, 그렇다면 몇 개가 필요한지 저장- ...
3KG x 7개일 때,5KG으로 정확히 나누어지는지, 그렇다면 몇 개가 필요한지 저장
이러한 과정으로 풀면 될 것이다.
결과적으로, 답은 3KG x 2개, 5KG x 3 으로, 최소 설탕 봉지는 5 개가 될 것이다.
Answer 1 - Brute Force 방식
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
// 최소값 비교를 위해 가장 높은 숫자로 미리 배정.
int min = Integer.MAX_VALUE;
// 3 키로짜리 설탕 봉지 0개에서 시작하여,
for(int KG3 = 0; KG3 * 3 <= N; KG3++) {
// 3KG 짜리 설탕 봉지를 빼고 남은 설탕의 무게.(KG)
int remain = N - (KG3 * 3);
// 남은 양이 정확히 5로 떨어진다면,
if(remain % 5 == 0) {
// 설탕 5KG 짜리가 몇 개 나오는지 계산.
int KG5 = remain / 5;
// 만약 현재 3키로, 5키로 설탕 봉지의 합이 "현재까지의" 최소 봉지보다 적다면, 교체한다.
min = (KG3 + KG5) < min ? (KG3 + KG5) : min;
}
}
// 만약, 한 번도 나누어 떨어진 적이 없다면, 해당 무게는 배송이 불가능하다.
if(min == Integer.MAX_VALUE) {
System.out.println(-1);
} else {
System.out.println(min);
}
}
}2 번째 풀이 방식 (Dynamic Programming - DP)
사실, 이 방식은 요구 설탕의 최대 크기가 100,000 정도 되며,
배달해야 할 설탕의 개수 또한 10,000 ~ 100,000 정도 될 때 굉장히 유용하게 절약 할 수 있다.
그래서 위의 가정을 어떻게 DP 로 풀어내는가?
결국에 "이전의 값을 저장" 하며, "계산을 최소화" 해 주기 위해서는,
최소값을 저장 해 두는 1 차원 배열이 필요하다.
0 부터 시작해서, 설탕을 전달해야 할 최대 KG 까지 배열 길이를 생성한다. (Length == 5001)
그리고, 0 부터 시작해서, 5001 인덱스를 KG 처럼 생각해서, 차례로 계산한다.
이 방식은 첫 번째 방식보다는 당연히 느리다. 바로 계산하기 때문이다.
하지만, 동일한 입력이 100,000 수준이라면, 기억해 두고 계산하는 것이 중요 할 것이다.
그렇다면, 각 인덱스(KG) 에서 처리될 과정을 생각 해 보자.
0 ~ 10 까지는 직접 작성해 두자.
Answer 2 - DP 방식
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 배달해야 할 총 설탕의 KG
int N = Integer.parseInt(br.readLine());
// DP 를 위한 1 차원 배열 - 최대 입력값까지 생성.
int[] dp = new int[5001];
// 10 KG 까지 최소값을 저장.
dp[0] = 0;
dp[1] = -1;
dp[2] = -1;
dp[3] = 1;
dp[4] = -1;
dp[5] = 1;
dp[6] = 2;
dp[7] = -1;
dp[8] = 2;
dp[9] = 3;
dp[10] = 2;
// 미리 KG 에 따른 최소값을 저장해 두기 위한 반복문
for(int i = 11; i <= 5000; i++) {
dp[i] = -1;
// 현재 인덱스가 현재 KG 을 의미한다.
int currKG = i;
// 5KG 몫 저장
int KG5 = currKG / 5;
// 음수가 아닐 때 까지 진행. - 최대 5KG 봉지 수에서 하나씩 줄여가며 체크
while (currKG >= 0) {
// 5KG 봉지를 빼고 남은 설탕 무게.
int remain = i - (KG5 * 5);
// 현재 남은 설탕에서 3으로 나누어진다면,
if(remain % 3 == 0) {
// 현재 5KG 설탕 봉지 + 3KG 설탕 봉지가 최소 값이다.
dp[i] = KG5 + (remain / 3);
break;
}
// 딱 나누어지지 않기 때문에, 5KG 봉지를 하나 뺀다.
KG5--;
}
}
// 최소값까지 이미 계산해 놓은 상황에서, 주어진 "N" 키로를 바로 출력한다.
System.out.println(dp[N]);
}
}위의 방식은 DP 방식의 극히 일부일 뿐이다.
이전의 계산 결과를 토대로,
현재 입력된 값에 대한 결과를 최대한 빠르게 계산하는 것이 DP 의 종류 중 하나이다.
논외
1 번째 방식과 2 번째 방식 모두 계산 시간, 사용 메모리가 거의 동일하다.
분명히 DP 방식이 더 많은 시간과 메모리를 할애해야 하지 않나? 생각이 든다.
결과는, 루프가 그리 크지 않기 때문에 실행 시간과 메모리에서의 이점이 거의 없다고 한다.
위의 의문은 GPT 를 통해 해결했습니다.