백준 2839번: 설탕 배달[C++]

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

2839번: 설탕 배달

코드

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	
	int a, b, min = 5000; // a is number of 3kg and b is number of 5kg
	
	for(a = 0; a * 5 <= n; a++){
		if((n - (5 * a)) % 3 == 0){
			b = (n - (5 * a)) / 3;
			min = a + b < min ? a + b : min; 
		}
	}
	if(min == 5000) min = -1;
	
	cout << min;
	
}

 

풀이

크게 특별한 생각없이 푼 문제였다.

3kg 와 5kg 짜리가 있으니, 가능한 모든 경우의 수를 대입해서 가장 적은 주머니를 갖는 경우를 찾았다.

5kg 짜리를 0개부터 시작해서 주어진 무개의 최대치까지 개수를 늘려보고

각 개수에서 3kg짜리가 딱 나누어지게 들어가는지를 확인해서 들어가면 그 때의 주머니 수를 확인한다.

그때의 주머니 수가 현재까지의 최저 주머니수보다 작다면 교체하고 아니라면 유지.

DP로도 풀 수 있고 Greedy로도 풀 수 있고 다른 분들의 해법을 보니 꽤 다양한 방법으로 접근이 가능한 문제인듯하다.