백준 3595: 맥주 냉장고

[문제 위치]

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

3595번: 맥주 냉장고

[문제]

맥주를 좋아하는 창영이는 냉장고에 맥주를 보관한다. 일반 냉장고에 음식과 맥주를 함께 보관하다보니 창영이의 냉장고에는 맥주를 넣을 곳이 점점 없어지고 있었다. 창영이는 맥주 전용 냉장고를 만들기로 결심했다.

창영이가 만들 냉장고는 a × b × c 크기의 직육면체이고, n개의 맥주 박스를 보관할 수 있다. 맥주 박스는 크기가 1 × 1 × 1인 정육면체이다. 창영이는 맥주를 신선하게 보관하기 위해서, 냉장고의 겉넓이를 가능한 작게 만들려고 한다.

예를 들어, 냉장고의 용량이 12라면, 다음과 같은 네가지 냉장고를 만들 수 있다.

 

크기	겉넓이
3 × 2 × 2	32
4 × 3 × 1	38
6 × 2 × 1	40
12 × 1 × 1	50

이 경우에 가장 좋은 냉장고는 3 × 2 × 2이다.

n이 주어졌을 때, 창영이가 만들 가장 좋은 냉장고(겉넓이가 가장 작은 냉장고)의 크기를 구하는 프로그램을 작성하시오.

 

[입력]

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 10⁶)

 

[출력]

첫째 줄에 a b c를 출력한다. 만약 겉넓이가 가장 작은 냉장고가 여러 가지인 경우, 아무거나 출력한다.

 

[알고리즘 분류]

-수학

-브루트포스 알고리즘

 

[문제 풀이]

브루트 포스 알고리즘을 통하여 모든 경우의 수를 계산하여 그 중 값이 가장 작은 경우를 출력하도록 한다.

#include <iostream>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
int main() {
    fastio;

    int n;
    cin >> n;

    long min = 100000001;
    int num[3];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            if (i * j > n) break;
            for (int k = 1; k <= j; k++) {
                if (i * j * k > n) break;
                if (i * j * k == n) {
                    long sum = i * j + j * k + k * i;
                    if (sum < min) {
                        min = sum;
                        num[0] = i;
                        num[1] = j;
                        num[2] = k;
                    }
                }
            }
        }
    }
    for (int i = 0; i <= 2; i++) cout << num[i] << " ";
}