[백준 2839] 설탕 배달

이 문제는 두 방법으로 풀 수 있다.

 

1. 그리디

 

최대한 적게 == 5kg으로 최대한 많이

 

따라서 케이스는

5*A

3*B

5*A + 3*B

-1

 

이렇게 4가지가 가능하다

 

따라서 N/5 부터 시작해서 0까지 돌면서 최적값을 찾으면 된다

 

N최대값이 5000이므로 최악의 경우에 1000번 돌기 때문에 1초안에 충분히 해결가능하다

 

 

2. dp

 

min ( dp[i-3] + 1, dp[i-5] + 1)

 

둘 중 하나인데 신경써야할 부분이 -1일때이다

 

하지만 좀만 끄적이면 -1은 7을 마지막으로 안나오는걸 알 수 있다.

7+5인 12까지만 직접 때려넣고 나머지 5000까지 알아서 채우게 하면 된다

 

12까지 채우는 이유는 12까지는 min식으로 하면 답이 있어도 -1로 배정되기 때문

 

13부터는 13-5 해도 8이기 때문에 -1이 안나온다. 

 

근데 이렇게 할바에는 그냥 그리디로 하는게 나은듯?

 

---

 

#include <iostream>

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N; cin >> N;

	if (N % 5 == 0) {
		cout << N / 5; return 0;
	}

	for (int i = N / 5; i >= 0; i--) {
		int kg = 5 * i;
		if ((N - kg) % 3 == 0) {
			cout << kg / 5 + (N - kg) / 3;
			return 0;
		}
	}

	cout << -1;
	return 0;
}

 

---

#include <iostream>
#define SIZE 5001

using namespace std;

int dp[SIZE] = { 0,0,0,1,-1,1,2,-1,2,3,2,3,4 };

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	
	for (int i = 13; i <= 5000; i++) dp[i] = min(dp[i - 3] + 1, dp[i - 5] + 1);

	int N; cin >> N;
	cout << dp[N];

	return 0;
}