[백준] 2839번 : 설탕 배달 - 자바(JAVA)

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

2839번: 설탕 배달

 

문제 해석

설탕을 정확하게 N 킬로그램 배달해야 한다.

설탕 봉지는 3kg 와 5kg 봉지가 있다.

최대한 적은 봉지를 들고 가려고 할 때 봉지 몇 개를 들고 가야 할까?

정확하게 N킬로그램을 만들 수 없다면 -1을 출력합니다.

 

문제 풀이 전 설계

N의 범위가 3~5000이기 때문에 완전탐색으로 하기는 힘들 것 같습니다.

최대한 적은 봉지를 들고가야 하기 때문에 5kg 봉지를 들고 가는 것이 제일 좋습니다.

 

우선 정확하게 N킬로그램이 가능한지부터 판별해야 합니다.

3x + 5y = N이 성립해야 합니다.

 

N이 1,2일때는 N킬로그램이 불가능합니다.

N = 3 일때는 3kg 봉지 하나를 들고 갈 수 있습니다.

N = 4일때도 N킬로그램은 불가능합니다.

N = 5일때는 5kg 봉지 하나를 들고 갈 수 있습니다.

N = 6일때는 3kg 봉지 2개를 들고 갈 수 있습니다.

N = 7일때는 N킬로그램은 불가능합니다.

N = 8일때는 3kg 봉지 하나를 들고 갈 수 있습니다. + 5kg 봉지 하나를 들고 갈 수 있습니다.

N = 9일때는 3kg 봉지 3개를 들고 갈 수 있습니다.

 

이전에 구한해를 통해 현재 정답을 구하는 DP느낌이 듭니다.

 

N = 6일때를 보면 6은 (1+5) , (2+4) , (3+3)으로 볼 수 있습니다.

따라서 N6 = (N1 + N5) , (N2 + N4) , (N3 + N3) 중 최솟값입니다.

따라서 불가능한경우를 제외한 N3 + N3 은 2로 최솟값은 2입니다.

 

N = 8일때는 8은 (1+7), (2+6) , (3 + 5) , (4+4)로 볼 수 있습니다.

따라서 N8 = (N1+N7) , (N2+N6), (N3+N5), (N4+N4) 중 최솟값입니다.

따라서 불가능한 경우를 제외하게 되었을 때 N3 + N5 = 2입니다.

 

이렇게 dp 배열을 채워나가면서 N이 목적 값 도달하였을 때의 dp의 배열의 크기가 바로 정답입니다.

DP [x] = Integer.Max_Value는 불가능을 의미합니다.

 

 

 

DP [i-j] 대신에 DP [N-j]를 사용해서 디버깅하는데 엄청 오래 걸렸습니다..

 

코드

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

public class Main_2839_설탕배달 {

	
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		int []DP = new int[N+1];
		
		Arrays.fill(DP, Integer.MAX_VALUE);
		if(N>=3)DP[3] = 1;
		if(N>=5)DP[5] = 1;		
						
		for(int i=6; i<=N; i++) {			
			for(int j=1; j<=i/2; j++) {								
				if(DP[j] ==Integer.MAX_VALUE || DP[i-j] ==Integer.MAX_VALUE) {
					continue;
				}																
				DP[i] = Math.min(DP[i], DP[j] + DP[i-j]);				
			}
		}
		if(DP[N] ==Integer.MAX_VALUE) {
			System.out.println(-1);
			return;
		}
		System.out.println(DP[N]);
	}

}