[백준/boj] 2839: 설탕 배달 (Java) / DP / 그리디

문제

2839번: 설탕 배달

 

DP(다이나믹 프로그래밍)를 이용한 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main { 
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	public static void main(String[] args) throws Exception {
		int N = Integer.parseInt(br.readLine());
		int[] dp = new int[N + 1];
        
		if (N >= 3)
			dp[3] = 1;
		if (N >= 5)
			dp[5] = 1;
		
        for (int i = 6; i <= N; i++) {
			if (i % 5 == 0) {
				dp[i] = dp[i - 5] + 1;
			} else if (i % 3 == 0) {
				dp[i] = dp[i - 3] + 1;
			} else {
				if (dp[i - 3] != 0 && dp[i - 5] != 0) {
					dp[i] = Math.min(dp[i - 3], dp[i - 5]) + 1;
				}
			}
		}
		
        if (dp[N] == 0) {
			System.out.println("-1");
			return;
		}
		System.out.println(dp[N]);
	}
}

• 먼저 dp 배열에는 인덱스 킬로그램을 배달해야할 때, 몇개의 봉지가 필요한지를 담는다. (dp[3] => 3킬로그램을 배달 해야할 때, 필요한 봉지 개수)
• dp[3] 과 dp[5] 는 1로 초기화 해준다. (1개의 봉지로 가져갈 수 있다)
• for 문에서 6부터 N까지 (N>= 6) 하나씩 증가시키면서 dp 배열을 채운다.
  1. 먼저 5킬로그램 봉지가 많을 수록 더 적은 봉지를 사용하기 때문에 i가 5의 배수인지 먼저 확인하고, 5의 배수이면 i-5 킬로그램일 때의 봉지 개수(dp[i-5])에 +1 해준다.
     • 예를 들어 15킬로 그램일때 3의 배수인지 먼저 확인하면 5가 들어가지만, 5의 배수인지 먼저 확인하면 3이 들어간다.
  2. i가 5의 배수가 아니라면 3의 배수인지 확인한다. 3의 배수라면 i-3 킬로그램일 때의 봉지 개수(dp[i-3])에 +1 해준다.
  3. i가 5의 배수도, 3의 배수도 아니라면 ! i 킬로그램 보다 3 킬로그램 적을 때(dp[i-3])와 5 킬로그램 적을 때(dp[i-5]) 봉지 개수를 확인 한 후, 둘다 0이 아니면 둘 중 더 적은 봉지를 사용한 경우에 +1 을 해주면 된다.
     • 계속 최소 봉지 개수를 담아왔기 때문에 둘 중 적은 봉지 개수 +1 을 해주는 경우가 가장 적은 봉지 개수로 설탕을 담은 경우이다.

 

이중 for문을 이용한 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main_BOJ_2839_설탕배달2 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	public static void main(String[] args) throws Exception {
		int N = Integer.parseInt(br.readLine());
		for(int i=0; i<=N/3; i++) {
			for(int j = 0; j<=N/5; j++) {
				if( i*3 + j* 5 == N) {
					System.out.println(i+j);
					return;
				}
			}
		}
		System.out.println("-1");
	}
}

이 풀이는 한달 전에 파이썬으로 풀었던 것을 자바로 풀어보았다 !

이중 for문에서 안쪽 for문의 j는 5의 몫이 되고 , 바깥쪽 for문의 i는 3의 몫이 된다. 

먼저 안쪽 for문에서 최대한으로 5의 배수를 만들어 N 이 안나온다면 바깥쪽 for문의 i값을 증가시키는 방식이다. 즉, 3 킬로그램의 봉지개수를 최소로 하면서 N 킬로그램을 만족하는 봉지 개수를 찾아간다. 만약 이중 for문을 빠져나왔다는 것은 봉지에 정확하게 담을 수 없다는 것을 의미한다.