백준 2839 설탕 배달

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

2839번: 설탕 배달

 

- 2가지의 풀이법이 있다. Greedy, DP

 

- Greedy 풀이법을 보면, 주어진 N에 3을 빼주면서, 뺄 때마다 해당 수가 5의 배수인지를 확인한다. 5의 배수가 되는 순간 남은 모든 무게를 5kg 봉지로 해결하면 되므로 그것이 해답이다.

 

#include <iostream>

using namespace std;

int N;
int main() {
	cin >> N;
	int ans = 0;
	while (N >= 0) {
		if (N % 5 == 0) {	
			ans += (N / 5);	
			cout << ans << endl;
			return 0;
		}
		N -= 3;	//3kg을 빼고 
		ans++;	//가방 하나 늘어남
	}
	cout << -1 << endl;
}

 

 

 

- 5로 나누어 떨어지는 경우가 없었어도, 3으로 계속 뺐을 때 N이 0이 된다면 어쨌든 3kg만으로 해결이 가능한 경우이므로 답이 된다. 하지만 N이 음수가 된다면 해결이 불가능한 문제이므로 -1을 return한다.

 

- DP 풀이법은, 점화식 dp[i]를 'ikg을 옮기고자 할 때 최소한의 봉지 갯수'로 정한다. 그 후, dp[3]과 dp[5]는 1이고, 6부터 n까지 for문을 돌리면서 만약 dp[i-3]이 존재하면 +1값을 대입하고, dp[i-5]값이 존재하면 해당 값과 dp[i-3]+1을 비교해서 더 작은 수를 대입한다. 물론 dp[i]가 존재하지 않으면 바로 dp[i-5]+1을 넣는다.

 

#include <iostream>
#include <algorithm>
using namespace std;
int dp[5001];
int main() {
	int n;
	cin >> n;
	dp[3] = dp[5] = 1;
	for (int i = 6; i <= n; i++) {
		if (dp[i - 3]) dp[i] = dp[i - 3] + 1;
		if (dp[i - 5]) dp[i] = dp[i] ? min(dp[i], dp[i - 5] + 1) : dp[i-5]+1;
	}
	if(dp[n]) cout << dp[n];
	else cout << -1;
	return 0;
}