2839번: 설탕 배달
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그
www.acmicpc.net
문제 설명
설탕 3kg, 5kg 봉지가 있는데 특정 kg수를 봉지를 최대한 적게 사용하여 만드려고 할때 가장 적게 쓰는 봉지의 수를 구하는 문제입니다.
18kg를 3kg봉지와 5kg봉지를 사용하여 채우려면 3kg짜리 6개를 써서 18kg를 만들 수도 있습니다.
하지만 5kg 짜리 3개와 3kg짜리 1개를 사용하여 만들면 총 4개의 설탕봉지를 사용합니다. 그러니까 4가 답이되는 것입니다.
3kg와 5kg만 사용하므로 만들 수 없는 수도 존재합니다. 그럴때는 -1을 출력하는 문제입니다.
입력은 채우는 설탕의 kg수 N이 주어지고 N의 범위는 3이상 5000이하(3<= N <=5000)입니다.
몇가지 입력에 대한 출력을 먼저 보고 문제를 풀어보시고 풀이를 봐주세요.
| INPUT | OUTPUT |
| 19 | 5 |
| 20 | 4 |
| 91 | 19 |
| 4999 | 1001 |
| 7 | -1 |
풀이1 - DP
두가지 풀이가 있습니다. 전형적인 DP방식의 풀이와 그리디한 방식으로 푸는 방법이지요. 첫번째 풀이는 DP를 사용한 풀이입니다.
만약 현재 i kg를 달성하려면 이 전에 계산한 (i-3)kg와 (i-5)kg 중 작은 것에 1을 더하면 현재 i kg을 채울 수 있는 최소의 봉지수가 나오겠네요.
dp[i] = min(dp[i-3] + 1, dp[i-5] +1)
그런데 만들 수 없는 수는 0이겠죠? 예를 들면 4는 절대로 3과 5를 조합하여 만들 수가 없는데요. 그러면 항상 0이 최소의 수가 되니까 조건을 달아야합니다.
만약 dp[i-3]에 0보다 큰 값이 있을때, dp[i-5]일때 0보다 큰 값이 있을때 만 계산하게 만드는 것입니다.
코드는 아래와 같습니다.
#include <iostream>
using namespace std;
int dp[5001]; //global 변수이기때문에 0으로 초기화된 배열
int main() {
int n;
cin >> n;
//3kg와 5kg를 만드는 가장 최소의 봉지수는 1
//따라서 dp[3]과 dp[5]는 무조건 1
dp[3] = dp[5] = 1;
//3과 5 다음인 6부터 for loop 순회
for (int i = 6; i <= n; i++) {
if (dp[i - 3]) dp[i] = dp[i - 3] + 1;
//이미 dp[i-3]에 값이 존재할때 dp[i]가 업데이트 됐었을 수 있다.
//만약 dp[i]에 값이 없다면 dp[i] = dp[i-5] +1 로 업데이트
if (dp[i - 5]) dp[i] = dp[i] ? min(dp[i] , dp[i - 5] + 1) : dp[i - 5] + 1;
}
cout << (dp[n] == 0 ? -1 : dp[n]) << endl;
return 0;
}
먼저 dp라는 배열을 0으로 셋팅해놓고 (전역변수이기 때문에 저절로 0으로 초기화됩니다.) dp[3] = dp[5]를 1로 만든 후에 앞서 설명한 것을 for문 안에 구현하면 됩니다.
풀이2 - Greedy
설탕이 25kg가 있다면 5kg로만 계속 사용하여 채우면 됩니다. 그러면 5개 봉지만 사용하면 되겠네요. 그렇다면 우리가 kg을 사용할 일이 굳이 있을까요? 우리가 5kg으로 모두 채울 수 있다는 것을 미리 알면 오히려 3kg를 사용하면 불리하다는 것을 알 수 있습니다. 그렇다면 5kg으로 나눠진다는 것만 알면 되지 않을까요? 이때 mod연산 %연산이 사용됩니다. %5 연산을 하여 0이 되지 않는다면 3kg를 봉지를 사용해야겠죠.
그리고 난 후 다시 5kg로 나눠 떨어지는지 확인합니다. 만약 나눠떨어지면 나눈 몫만큼의 5kg봉지가 사용되고 프로그램을 바로 종료시키면 되는 아이디어입니다.
전체 C++ 소스코드는 아래와 같습니다.
#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;
}
두가지 방식의 풀이를 알아보았는데 저도 얼핏 dp만 생각하고 있었는데 다른 사람의 해답을 보니 이러한 방법이 있다는 것을 알았습니다. 역시 저빼고 다른 사람들은 똑똑한것 같습니다.
'알고리즘 > DP' 카테고리의 다른 글
| [알고리즘:DP] 백준(BOJ) 9251번 LCS (0) | 2019.01.28 |
|---|---|
| [알고리즘] 동전 교환 알고리즘 개념, 구현 (0) | 2018.11.24 |
| [알고리즘] 배낭 알고리즘(Knapsack algorithm) 기본 개념과 구현 방법 (1) | 2018.10.21 |
| [알고리즘] 백준 온라인 저지 BOJ 1912 : 연속합 (0) | 2018.09.24 |
| [알고리즘] 백준 온라인 저지 BOJ 1463: 1로 만들기 (0) | 2018.09.23 |
REAKWON
와나진짜
