[다이나믹 #1] 백준 2839번: 설탕 배달JAVA

2839번: 설탕 배달

문제

---

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 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

 

 

풀이

---

 이 문제는 그리디알고리즘 문제에서도 나온 문제인데, 이번에는 다이나믹프로그래밍 기법으로 풀어야 하는 문제이다. 다이나믹 프로그래밍은 dp테이블을 어떻게 활용할지 정의하고, 점화식을 세우는게 가장 중요하다.

 

 나는 dp테이블을 입력받은 kg의 크기 n+1(0은 안쓰기 위해)만큼 배열을 생성하고, 각 인덱스에 저장할 값을 해당 인덱스의 크기를 담을 수 있는 봉투의 최소개수로 정의를 했다. 예를들어 인덱스5에는 5kg을 담을 수 있는 봉투의 최소개수이고, 인덱스 13에는 13kg을 담을 수 있는 봉투의 최소 개수가 저장 될 것이다.

 

 dp테이블을 INF숫자인 9999로 정의해서 전부 초기화 한다음에 점화식을 다음과 같이 세웠다. (INF가 저장되어 있으면 최종적으로 3, 5로 만들 수 없는 숫자임을 의미한다.)

 

dp[i] = min(dp[i-5], dp[i-3]) + 1

 

 이 점화식은 해당 인덱스일때 5kg전과 3kg전의 두값을 비교해서 작은값에 1을 더한값이 해당 인덱스를 담을 수 있는 최소 봉투 개수이다. 하지만 조건이 있다. 5kg전과 3kg전의 값이 둘다 INF일 경우 현재 인덱스를 만들 수 없는 경우가 되므로 현재 인덱스도 INF로 나둬야 하기 때문에 이조건을 고려해야 한다. [자세한건 코드 참고]

 

 

갓벨의 겜.프.독

 많은 사람들이 위와 같은 방법으로 풀은 것 같은데, 아래와 같은 코드가 다이나믹프로그래밍을 잘 활용한 좀 더 직관적인 방법이 아닐까 생각한다.

코드

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

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));
		
		final int INF = 9999;
		int n = Integer.parseInt(br.readLine());
		int dp[] = new int[n+1];
		
		Arrays.fill(dp, INF);
		
		if(n>=3) {
			dp[3] = 1;
			if(n>=5) {
				dp[5] =1;
			}
		}
		
		if(n>=6) {
			for(int i=6; i<=n; i++) {
				if(dp[i-5] == INF && dp[i-3] == INF) {
					continue;
				}
				dp[i] = Math.min(dp[i-5], dp[i-3])+1;
			}
		}
		
		
		if(dp[n] == INF) {
			bw.write(String.valueOf(-1));
		}else {
			bw.write(String.valueOf(dp[n]));
		}
		bw.flush();
		bw.close();
	}
}