[BOJ] 2545: 팬케익 먹기(Python)

2545번: 팬케익 먹기

문제 설명

박스 모양의 팬케익이 있을 때, 한쪽 면을 두께 1cm씩 D번 잘라내려고 한다. 잘라낸 후의 팬케익 부피의 최댓값을 구해보자.

나의 풀이

import sys
input=sys.stdin.readline
    
def func():
    _=input()
    a,b,c,d=map(int,input().split())
    if d==0:
        return a*b*c
    a,b,c,=sorted((a,b,c))
    cake=sum([a,b,c])-d
    tmp=min(cake//3,a)
    ta=tmp
    cake-=tmp
    tmp=min(cake//2,b)
    return ta*tmp*(cake-tmp)

t=int(input())
for _ in range(t):
    print(func())

케이크를 최대한 같은 높이로 만들어주는 것이 부피를 최대화할 수 있는 방법이다. 각 면의 길이를 모두 더해 D만큼 제외해 3으로 나누면 가장 비슷한 높이가 된다.

주의할 점은 면의 길이 중 가장 비슷한 높이보다 짧은 길이가 존재할 수 있다는 점이다. 따라서 둘 중 작은 길이를 기준으로 길이를 설정해야 한다.

시간복잡도

면이 3개밖에 없고 단순 연산이므로 O(1)이다.