[백준] 2839 설탕 배달(C++)

 

문제 URL:

2839번: 설탕 배달 (acmicpc.net)

2839번: 설탕 배달

 

다음 문제는 3킬로그램 봉지와 5킬로그램 봉지를 사용하여 주어진 N킬로그램만큼의 설탕을 배달해야 할 때, 

봉지 몇 개를 가져가면 되는지 그 수를 구하는 문제로 봉지의 최소 개수를 출력해야 한다.

만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

 

이 문제를 처음 풀 때는 단순히 N킬로그램에서 계속해서 3을 빼주며 5로 나누어지는 지 확인하는 방식으로 문제를 풀었는데

문제에 다이나믹 프로그래밍을 이용할 수 있다는 것을 알고 다이나믹 프로그래밍을 사용하여 다시 문제를 풀었다. 

코드는 아래와 같다. 

---

<첫 번째 시도>

#include<iostream>
using namespace std;

int main() {
    int n, result=0, count;
    cin >> n;
    
    for(int b=0; b<5; b++) {
        count = b;  // 3킬로그램 설탕 봉지의 개수
        if((n-3*b)<=0)  // 정확한 N킬로그램을 만들 수 없는 경우
            break;
        if((n-3*b)%5==0) {  // N킬로그램이 만들어진 경우
            result = (n-3*b)/5;
            break;
        }
    }
    
    if(result == 0 && n%3 == 0)  // 3킬로그램 봉지만으로 N킬로그램을 만드는 경우
        cout << n/3;
    else if(result == 0)  // 정확한 N킬로그램을 만들 수 없는 경우
        cout << -1;
    else  // 정확한 N킬로그램이 만들어진 경우
        cout << result + count;
        
	return 0;
}

 

<두 번째 시도>

#include <iostream>
using namespace std;
int dp[5001];

int main() {
	int n;
	cin >> n;
    
	// 3킬로그램과 5킬로그램을 만드는 봉지의 최소 개수는 1
	dp[3] = dp[5] = 1;	

	for (int i = 6; i <= n; i++) {
		if (dp[i - 3])  // N이 3의 배수일 때
			dp[i] = dp[i - 3] + 1;

		// dp[i]가 0이 아닐 경우, 기존 dp[i]와 dp[i-5]+1를 비교하여 작은 값으로 업데이트
		if (dp[i - 5])  // N이 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;
}