BOJ 2545 - 팬케익 먹기

문제

세 종류의 팬케익이 각각 a, b, c개 있고, d개를 먹어야 할 때 남은 팬케익의 곱을 최대화하라.

입력

테스트 케이스 수 T와 각 케이스마다 a, b, c, d가 주어진다.

출력

각 케이스마다 남은 팬케익 세 값의 곱의 최댓값을 출력한다.

예제

입력	출력
`1` `3 5 7 6`	`27`

풀이

그리디하게 남은 양을 최대한 균등하게 분배하여 곱을 최대화한다.

세 값을 정렬하여 작은 순서로 배치한다
남은 총량 sum - d를 가장 작은 값부터 균등하게 할당한다
가장 작은 값에 남은양 / 3을, 두 번째에 나머지의 1/2를, 세 번째에 최종 잔여를 배분한다
세 값의 곱을 출력한다

핵심 아이디어: AM-GM 부등식에 의해 합이 고정일 때 곱은 세 수가 균등할수록 최대이므로, 작은 값부터 균등 분배한다.

코드

#include <iostream>
#include <algorithm>
 
using namespace std;
typedef long long ll;
 
int t;
ll a[5], d;
 
int main()
{
  scanf("%d", &t);
  while (t--)
  {
    scanf("%lld %lld %lld %lld", &a[0], &a[1], &a[2], &d);
    sort(a, a + 3);
    ll tmp = a[0] + a[1] + a[2] - d;
    if (a[0] >= tmp / 3)
      a[0] = tmp / 3;
    tmp -= a[0];
    if (a[1] >= tmp / 2)
      a[1] = tmp / 2;
    tmp -= a[1];
    a[2] = tmp;
    printf("%lld\n", a[0] * a[1] * a[2]);
  }
}

복잡도

시간: O(T)
공간: O(1)

문제