[백준 2839] 설탕 배달 (S4)

📍 문제 

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

 

📍 문제 풀이

 

배달하는 봉지의 최소 갯수를 찾기 위해서는 우선 5kg짜리로 가져갈 수 있는지 먼저 확인하고 3kg를 확인해야한다.

만약 설탕의 무게가 5kg로만 모두 가져갈 수 있다면 그 방법이 최소

그게 아니라면 3kg로 가져가야한다.

 

이 기본적인 로직을 가지고

1. 반복문 이용

2. DP 이용

두가지 방식으로 풀 수 있다.

 

📍 전체 코드

반복문 이용

import java.util.Scanner;

public class boj_2839 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int sugar = sc.nextInt();

		int result = 0;
		while (sugar > 0) {
			if (sugar < 3) {
				System.out.println(-1);
				return;
			}
			if (sugar % 5 == 0) {
				result += (sugar / 5);
				System.out.println(result);
				return;
			}
			sugar -= 3;
			result++;
		}
		System.out.println(result);
	}
}

 

DP 이용

import java.util.Arrays;
import java.util.Scanner;

public class boj_2839 {
	static final int maxVal = 9999;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int sugar = sc.nextInt();

		if (sugar < 5) {
			if (sugar == 3) {
				System.out.println(1);
			} else {
				System.out.println(-1);
			}
			return;
		}

		int[] dp = new int[sugar + 1];
		Arrays.fill(dp, maxVal);
		dp[3] = dp[5] = 1;

		for (int i = 6; i < sugar + 1; i++) {
			dp[i] = Math.min(dp[i - 3], dp[i - 5]) + 1;
		}

		System.out.println(dp[sugar] > maxVal ? -1 : dp[sugar]);
	}
}