[C/C++]백준 2839번 - 설탕배달

 

 

 

문제 링크 : www.acmicpc.net/problem/2839

2839번: 설탕 배달

 

관련 알고리즘 : 그리디 알고리즘(탐욕 알고리즘), 동적 계획법

아이디어)

2가지 방법으로 풀어봤다.

 

그리디)

처음 설탕을 가져갈 때 5kg짜리로 최대한 많이 담고, 남은 설탕을 3kg으로 가져감.

만약 5kg으로 최대한 담고 3kg으로 나머지를 담는데, 나눠떨어지지 않으면 5kg를 하나 빼고 다시 3kg을 담음.

5kg를 다 뺐지만, 3kg만으로 설탕이 나눠지지 않으면, -1을 출력.

 

동적 계획법)cache[n] = min( cache[n-3] , cache[n-5]) + 1;입력받은 무게의 최소 설탕 봉지 개수를 구할 때, 주어진 무게에서 각각 3, 5를 뺐을 때 무게의 최솟값을 비교해서 더 작은 것을 선택한다.

 

단, 3이나 5를 뺀 무게중 하나의 cache값이 -1 이면, -1이 아닌 무게를 가져옴. 둘다 -1이면, cache에 -1을 저장.

Weight	1	2	3	4	5	6	~~~~~	n
Cache	-1	-1	1	-1	1	2	~~~~~	?

무게가 6일 때, 예를 들어보자.

Cache[6] = min ( Cache[6-3], Cache[6-5]) + 1;

을 하는데, 이전 Cache의 값이 -1 이라면, 나눠떨어지지 않는 경우이므로, -1이 아닌 값을 들고온다.

              

 

<그리디>

#include<iostream>

using namespace std;

int solution(int weight)
{
    int numFive = weight / 5;
    int tmp = 0;

    if (weight < 3) return -1;

    while (numFive != -1) {
        tmp = weight - (5 * numFive);

        if (tmp % 3 == 0) {
            return numFive + (tmp / 3);
        }
        numFive -= 1;
    }
    return -1;
}

int main()
{
    int weight;

    cin >> weight;
    cout << solution(weight) << endl;

    return 0;
}

 

<동적 계획법>

#include<cstdio>
#include<cstring>
int cache[5001];

int min(int a, int b)
{
	if (a == -1) return b;
	else if (b == -1) return a;
	else return a < b ? a : b;
}

int solve(int weight)
{
	cache[3] = 1;
	cache[5] = 1;

	int compare;

	for (int i = 6; i <= weight; i++) {
		compare = min(cache[i - 3], cache[i - 5]);
		if (compare == -1) cache[i] = -1;
		else cache[i] = min(cache[i - 3], cache[i - 5]) + 1;
	}
	
	return cache[weight];
}
int main()
{
	memset(cache, -1, sizeof(cache));
	int weight;
	int result;

	scanf("%d", &weight);

	result = solve(weight);
	printf("%d\n", result);

	return 0;
}

 

 

다른 문제들의 코드 : github.com/Ewlrma/Algorithm-Solution-

Ewlrma/Algorithm-Solution-