직육면체의 세 변(길이, 너비, 높이)의 합이 주어져 있을 때, 이 합을 이용해 직육면체의 최대 부피를 구하는 문제를 살펴보겠습니다. 직육면체는 길이(Length), 너비(Breadth), 높이(Height)의 세 변을 가지며, 부피는 세 변의 곱으로 계산됩니다.
직육면체의 부피 = 길이 × 너비 × 높이
핵심 아이디어는 간단합니다. 세 변의 값이 서로 최대한 가까울수록 부피가 커집니다. 이는 산술-기하 평균 부등식(AM-GM 부등식)에 따라 합이 고정되어 있을 때 곱은 각 값이 동일할 때 최대가 되기 때문입니다.
문제 이해하기
변의 합 S가 주어지고, 세 변을 L, B, H라고 합시다. 부피를 최대화하려면 세 변을 최대한 비슷하게 만들어야 합니다.
예제: S = 6일 때 가능한 조합은 다음과 같습니다.
[L=1, B=1, H=4] → 부피 = 4
[L=1, B=2, H=3] → 부피 = 6
[L=2, B=2, H=2] → 부피 = 8
참고: 다른 조합들도 같은 방식으로 계산할 수 있지만, L, B, H가 서로 가깝거나 같을 때 가장 큰 부피를 얻습니다.
입출력 예시 1
입력: S = 6
출력: 주어진 변의 합으로 만들 수 있는 직육면체의 최대 부피는 8입니다.
설명: 합 S를 세 변에 최대한 균등하게 나눠봅니다.
L = S/3 → (L = 2, 정수 부분, 남은 S는 4)
B = (S-L)/2 = (S-S/3)/2 → (B = 2, 남은 S는 2)
H = S-L-B = S-S/3-(S-S/3) → (H = 2, 남은 S는 0)
입출력 예시 2
입력: S = 10
출력: 주어진 변의 합으로 만들 수 있는 직육면체의 최대 부피는 36입니다.
설명: 마찬가지로 S를 세 변에 최대한 균등하게 나눕니다.
L = S/3 → (L = 3, 정수 부분, 남은 S는 7)
B = (S-L)/2 = (S-S/3)/2 → (B = 3, 남은 S는 4)
H = S-L-B = S-S/3-(S-S/3) → (H = 4, 남은 S는 0)
접근 방식
- 사용자로부터 변의 합(Sum)을 입력받습니다.
- 길이를 Sum/3(정수 나눗셈)로 계산한 뒤, Sum을 Sum − Length로 갱신합니다.
- 너비를 갱신된 Sum/2(정수 나눗셈)로 계산한 뒤, Sum을 Sum − Breadth로 갱신합니다.
- 마지막으로 남은 Sum을 높이로 지정합니다.
- 참고: 세 변을 계산하는 순서는 결과에 영향을 주지 않습니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int Maximize_Volume(int sumofsides){
int length,breadth,height;
length=breadth=height=0;
// 길이 계산
length = sumofsides / 3;
sumofsides -= length;
// 너비 계산
breadth = sumofsides / 2;
// 남은 합이 곧 높이
height = sumofsides - breadth;
return length * breadth * height;
}
// 메인 프로그램
int main(){
int sos = 12;
cout << "주어진 변의 합으로 만든 직육면체의 최대 부피는 "<<Maximize_Volume(sos) << endl;
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력을 얻을 수 있습니다.
주어진 변의 합으로 만든 직육면체의 최대 부피는 64
S = 12인 경우, 세 변이 L = 4, B = 4, H = 4로 완전히 동일해지므로 부피는 4 × 4 × 4 = 64가 됩니다. 이처럼 세 변을 균등하게 분배하는 간단한 그리디(Greedy) 기법만으로도 최대 부피를 효율적으로 구할 수 있습니다.