[Greedy] 백준 2839: 설탕 배달

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

2839번: 설탕 배달

 

분명히 브루트포스 문제집에서 건진 문제이고 문제에 대한 사족으로 "원래는 수학 카테고리에 있었는데 브루트포스로 옮겼다"고 까지 적혀 있는데 내가 쓴 재귀함수를 이용한 탐색에서는 틀렸다. 정확히는 예시+내가 만들어 본 case에 관해서는 답이 맞게 나왔는데 정작 채점을 돌렸을 때 시간초과가 났다.

 

문제를 포스팅하기 앞서 Greedy 알고리즘이란, 각 선택 단계마다 그 단계에서 당장 최적인 선택을 하는 것이다. Greedy 알고리즘으로 구한 해는 연산속도가 빠른 대신 그 답이 최적해인 것을 보장할 수 없는데, 다음 조건을 만족하는 경우에는 Greedy를 통해 구한 값이 최적해가 된다.

 

Greedy Choice Property: 현재 단계에서 선택이 다음 단계 선택에 영향을 미치지 않음. 내가 이번 단계에서 5kg짜리 설탕봉지를 고른다고 해서 다음 단계에서 5kg 설탕봉지를 고르는 데 제약이 생기지 않는다. 따라서 이 문제가 해당 조건을 만족한다.

 

Optimal Substructure: 매 순간 최적의 해가 문제 전체에 대한 최적의 해. 이 문제에서 5kg 봉지를 최대한 많이 쓰는 것이 사용되는 전체 봉지 수를 줄이는 방법이다. 주어진 N에 대해 매 단계에서 최우선적으로 5kg 봉지를 사용하고 그 후에 3kg 봉지에 선택권을 부과한다면 이는 결국 가장 최소로 사용되는 봉지 개수를 도출하는 길이다. 따라서 이 문제가 해당 조건을 만족한다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int bagNum = -1;

void findBagNum(int N, int threeKgBagNum, int fiveKgBagNum, int currentSugar)
{
    if (currentSugar > N)
    {
        return;
    }

    if (currentSugar == N)
    {
        if (bagNum == -1)
        {
            bagNum = (threeKgBagNum + fiveKgBagNum);
        }
        else
        {
            bagNum = min(bagNum, (threeKgBagNum + fiveKgBagNum));
        }

        return;
    }

    findBagNum(N, threeKgBagNum + 1, fiveKgBagNum, currentSugar + 3);
    findBagNum(N, threeKgBagNum, fiveKgBagNum + 1, currentSugar + 5);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N;
    cin >> N;

    int ans = 0;
    while (N >= 0)
    {
        if (N % 5 == 0)
        {
            ans += N / 5;
            cout << ans;
            return 0;
        }
        N -= 3;
        ans++;
    }

    cout << -1;
}

 정답 코드이다. 주어진 N에 대해 최우선적으로 최대한 많은 5kg 봉투를 사용한 다음, 남은 양에 대해 3kg 봉투를 사용하였다. 위에 있는 findBagNum은 내가 재귀함수로 접근해서 풀어보려고 하다가 시간 초과로 실패한 흔적인데, 혹시나 다른 때에 참고할 수도 있으니 같이 올린다.