[백준] 2839번 설탕 배달

https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

1.문제 분석

 어떤 N에 대해 3kg 가방과 5kg 가방 개수 조합이 여러개 있다고 하면 5kg 가방 개수가 더 많은 조합이 총 가방 갯수가 더 적을 것이다. 또한 N의 최대값이 5000밖에 안돼 모든 경우의 수를 다 고려해도 된다. 이때, 5kg 가방 개수가 적은 경우부터 찾기보다 많은 경우부터 찾는다면 정답은 더 빨리 찾을 수 있게 된다.

시간복잡도 계산

  N의 최대값이 5000이기 때문에 N이 5000일때, 5kg가방 개수는 최악의 경우 0 ~ 1000개의 경우를 고려해야한다. 따라서 최대 시간 복잡도는 아래와 같다.

시간복잡도 = O(1,000)

 

 

 

2. 코드

#include<iostream>
using namespace std;

#define ERROR_CANNOT_HANDLE -1
#define ERROR_NO_NEED_MORE_BAG5 -2

int getNumOfTotalBag(const int numOfBag5, const int N) {
    int leftWeight = N - (numOfBag5 * 5);
    if (leftWeight < 0) {
        return ERROR_NO_NEED_MORE_BAG5;
    }
    if (leftWeight % 3 != 0) {
        return ERROR_CANNOT_HANDLE;
    }

    int numOfBag3 = leftWeight / 3;
    return numOfBag5 + numOfBag3;
}

int main() {
    int result;
    int N;

    cin >> N;

    // 조금 더 빠른 검색을 위해, 5kg 가방이 많은 경우부터 고려한다.
    for (int numOfBag5 = N / 5; numOfBag5 >= 0; numOfBag5--) {
        result = getNumOfTotalBag(numOfBag5, N);
        if (result >= 0) {
            break;
        }
    }

    cout << result << endl;

    return 0;
}