[백준 / Java] 2839번: 설탕 배달 (실버4)

문제 풀이 날짜: 2023.08.02
포스트 작성일: 2023.08.02

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 2839번: 설탕 배달 (실버4)

 

키워드

그리디, 동적 계획법

 

풀이 접근법

• 그리디 또는 DP 중 택 1 하여 풀 수 있는 문제이다.
• 그리디 풀이법
  • 5kg 봉지를 먼저 세면 원하는 답을 구하기 쉽지 않다. 따라서 3kg을 먼저 고려한다.
  • 5kg을 먼저 빼지 않고, 3kg씩 계속 빼다가 5의 배수가 된다면 그 몫을 누적하고 종료하면 된다.
  • 그렇게 하지 않으면 3kg으로만 묶이는 경우의 수를 빠트리게 된다. (예: 9kg을 3kg 3봉으로 나타냄)
• DP 풀이법
  • 3의 배수, 5의 배수, 둘 다 아닌 경우로 나누어서 DP값을 갱신해간다.
  • 3의 배수도 5의 배수도 아닌 경우를 누락하지 않도록 주의한다. 이 경우는 3kg과 5kg 봉지를 혼합한 형태로 나타낼 수 있기 때문이다.
  • 3kg으로 묶었을 때보다 5kg으로 묶었을 때가 훨씬 개수가 적은 경우가 생길 수도 있다. 그렇기 때문에 Math.min()으로 계속 최솟값을 갱신해주어야 한다.
• 그 외
  • 문제에서 주어진 3, 5kg이 모두 소수이므로 소수의 특성을 이용해서 풀 수도 있다. 이 경우 O(1) 시간만에 해결 가능하다.

 

코드

1. 그리디로 푸는 경우

import java.io.*;

public class Main {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		int result = 0;
		while(N >= 0) {
			if(N % 5 == 0) {
				result += N / 5;
				System.out.println(result);
				return;
			}
			N = N - 3;
			result += 1;
		}
		
		System.out.println(-1);
	}
}

 

2. DP로 푸는 경우

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

public class Main {

	private static int MAX = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[] DP = new int[N + 1];
		
		Arrays.fill(DP, MAX);
		
		DP[3] = 1;
		if(N >= 5) {
			DP[5] = 1;
		}
		for(int i = 6; i <= N ; i++) {
			if(i % 3 == 0) {
				DP[i] = Math.min(DP[i - 3] + 1, DP[i]);
			}
			
			if(i % 5 == 0) {
				DP[i] = Math.min(DP[i - 5] + 1, DP[i]);
			} 
			
			if(i % 3 != 0 && i % 5 != 0) {
				if(DP[i - 3] != MAX || DP[i - 5] != MAX) {
					DP[i] = Math.min(DP[i - 3], DP[i - 5]) + 1;
				}
			}
		}
		
		if(DP[N] == MAX) {
			System.out.println(-1);
			return;
		}
		
		System.out.println(DP[N]);
	}

}

---

다양한 풀이가 가능한 문제이다. 문제에서 주어진 특정 매직 넘버들의 특징을 관찰하고 응용한다면 더욱 빠른 풀이를 구상할 수 있었다. 사용자 입력이 아닌 매직 넘버가 주어지는 문제의 경우 그 특성을 적극 활용하는 것이 좋겠다.

 

git 링크

(git 링크 첨부)