[수학/DP] 백준 2839 설탕 배달 - Python, Java

 

[ Contents ]

 

 

1. 문제 (링크 참조)

2839번: 설탕 배달

 

 

 

2. 문제 풀이

 주문시킨 설탕을 최대한 적은 봉지로 배달하는 문제입니다. 용량은 5kg와 3kg로, 최대한 5kg로 배달하는 게 좋습니다. 단, 주문량을 초과하거나 미달하면 안되며, 배달할 수 없는 경우는 -1를 출력합니다.

 

 

2022.01.19 - [Algorithm] - [Algorithm] 단골 1번 문제, 구현 / 수학

[Algorithm] 단골 1번 문제, 구현 / 수학

 DP맛 수학문제입니다. 마치 과학고 논술문제 같습니다. 과학고 지망생들은 미리 선행학습을 통해 미분을 알고 있지만, 중학교 논술시험이기 때문에 직접적으로 사용하진 않습니다. 그 대신, 중학교의 수학개념을 확장해서 미분을 사용합니다. 일차함수의 기울기를 구하는 것처럼, 아주 아주 조금 떨어진(△만큼) 두 좌표의 기울기를 계산하면 한 점에서의 기울기를 알 수 있다고 풉니다.

 이 문제도 마찬가지입니다. DP라는 알고리즘 기법을 알고 있으면 쉽게 풀 수 있습니다. 하지만 모르면 위의 서술처럼 천재적인 응용을 해야지만 풀 수 있습니다. 이 글에서는 마치 DP를 모르는 것처럼 응용해서 풀어보겠습니다.

 

 

 

3. 코드

N = int(input())
res = -1
five = 0

while(five * 5 <= N):
    if (N - five*5)%3 == 0:
        res = five + (N - five*5)//3
    five += 1
print(res)

 5kg봉지가 최대가 되면 좋을거라 생각해서, 무작정 N을 5로 나누면 안됩니다. 나머지가 0 또는 3의 배수가 되지 않으면 말짱도루묵입니다. 따라서 나머지를 확인하며 5kg봉지를 늘려가야 합니다. 

 5kg 봉지의 합이 주문량을 넘기 전까지, 5kg 봉지의 수를 늘려가며 나머지가 3으로 나누어 떨어지는지 확인합니다. 나누어 떨어지면, 사용한 봉지 수를 최소값으로 저장합니다.

 5kg 봉지 수가 점점 늘어나므로, 이후에 저장되는 값은 이전보다 무조건 작습니다.

 

 

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		sc.close();
		
		int a;
		int ans = -1;
		for (a = 0; a * 5 <= N; a++)
			if ((N - a * 5) % 3 == 0)
				ans = a + ((N - a * 5) / 3);
		System.out.println(ans);
	}
}