C++로 햄버거와 치킨버거 판매 시 최대 이익 구하는 프로그램

문제 설명

다섯 개의 정수 b, p, f, h, c가 주어진다고 가정해 봅시다. 어느 식당에서는 햄버거와 치킨버거, 두 가지 종류의 버거를 판매합니다. 햄버거를 만들려면 빵 2개와 소고기 패티 1개가 필요하고, 치킨버거를 만들려면 빵 2개와 닭고기 커틀릿 1개가 필요합니다. 현재 보유한 재료는 빵 b개, 소고기 패티 p개, 닭고기 커틀릿 f개이며, 햄버거는 h루피에, 치킨버거는 c루피에 판매할 수 있습니다. 이때 얻을 수 있는 최대 이익을 구하는 것이 목표입니다.

예시

입력이 b = 7, p = 5, f = 2, h = 10, c = 12라고 해봅시다. 이 경우 출력은 34가 됩니다. 햄버거 1개와 치킨버거 2개를 판매하면 수입이 1 × 10 + 2 × 12 = 34루피가 되어 이것이 가능한 최대 이익이기 때문입니다.

풀이 접근 방식

이 문제는 그리디(Greedy) 알고리즘으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

버거 하나를 만들 때마다 빵 2개가 필요하므로, 먼저 b를 2로 나누어 실제로 만들 수 있는 버거의 총 개수를 구합니다.
더 비싼 버거부터 우선적으로 판매해야 이익이 최대화됩니다. 따라서 치킨버거 가격(c)이 햄버거 가격(h)보다 높다면, 재료(p, f)와 가격(h, c)을 서로 맞바꾸어 항상 햄버거가 더 비싼 상태가 되도록 만듭니다.
먼저 더 비싼 버거를 빵과 패티 중 부족한 쪽에 맞춰 min(b, p)개 판매합니다.
남은 빵 max(b − p, 0)개로는 덜 비싼 버거를 min(남은 빵, f)개만큼 추가로 판매합니다.

알고리즘 단계

위 접근 방식을 의사코드로 표현하면 다음과 같습니다.

res := 0
b := b / 2
if h < c, then:
    swap p and f
    swap h and c
res := res + h * (minimum of b and p) + c * minimum of the (maximum of (b - p) and 0) and f)
return res

C++ 구현 예제

아래 코드를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;

int solve(int b, int p, int f, int h, int c) {
    int res = 0;
    b /= 2;
    if (h < c) {
        swap(p, f);
        swap(h, c);
    }
    res += h * min(b, p) + c * min(max(b - p, 0), f);
    return res;
}
int main() {
    int b = 7;
    int p = 5;
    int f = 2;
    int h = 10;
    int c = 12;
    cout << solve(b, p, f, h, c) << endl;
}

입력

7, 5, 2, 10, 12

출력

코드 동작 원리와 복잡도

solve 함수는 먼저 빵을 2로 나누어 만들 수 있는 버거 수를 계산합니다. 이후 치킨버거가 더 비싸다면 swap 함수로 재료와 가격을 교환하여 항상 햄버거 쪽이 더 높은 가격을 갖도록 정규화합니다. 그다음 더 비싼 버거를 min(b, p)개 판매하고, 남은 빵으로 min(max(b − p, 0), f)개의 저렴한 버거를 추가 판매해 총수입을 계산합니다.

모든 연산이 상수 번의 산술 및 비교 연산으로 이루어지므로 시간 복잡도는 O(1), 추가로 사용하는 공간 역시 O(1)입니다. 입력 크기와 무관하게 매우 빠르게 동작하는 효율적인 풀이입니다.