Nkg의 설탕을 5kg과 3kg의 봉지로 나누면 가장 적은 수의 봉지를 만드는 문제
https://www.acmicpc.net/problem/
– 1) 최소한의 자루는 제작해야 하므로 최대 5kg 자루부터 시작해서 점점 줄여나가는 식으로 욕심내서 해결할 수 있다.
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
void Solve(){
int n; cin >> n;
for(int i=n/5; i>=0; i--){
if((n-i*5)%3 == 0){
cout << i + (n-i*5)/3;
return;
}
}
cout << -1;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
Solve();
return 0;
}
– 2) DP(Dynamic Programming)로도 풀 수 있다.
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
int dp(5050);
const int MX = 5000;
void Solve(){
int n; cin >> n;
for(int i=1; i<=n; i++) dp(i) = MX;
dp(3) = dp(5) = 1;
for(int i=6; i<=n; i++) dp(i) = min(dp(i-3), dp(i-5)) + 1;
if(dp(n) >= MX) cout << -1;
else cout << dp(n);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
Solve();
return 0;
}