[백준] 2545. 팬케익 먹기

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

문제요약

• a,b,c가 주어지고 1회에 a,b,c 중 하나를 -1 시킴
• d회 수행했을때 남은 a x b x c 의 값을 최대로
• a,b,c,d : ${10^{18}}$

접근법

• a,b,c가 비슷해야 최대가 될 것 같음(웬지 그럴 것 같음)
• 1회 수행할때 가장 이득은 긴 쪽을 -1 시키는 것이 가장 이득
• 최대값에서 -1을 하는 방식으로 d회 수행하면 되는데
• 처음에는 상한선 x값을 찾는 이분탐색으로 진행했는데 구현이 까다로움
• a,b,c를 내림차순으로 정렬하고 3개의 case를 순차적으로 처리했음
  • a가 가장 클 때
  • a,b가 가장 클 때
  • a,b,c가 가장 클 때
  • 각각의 경우에서 d와 줄어들 값을 비교해서 처리했음

다른 접근법

• 검색으로 알게됨
• a,b,c의 합에서 d를 빼면 남아있는 것들의 합이 됨
• 남아있는 합을 적당히 비슷하게 3개로 나누면 됨