[BAEKJOON] 백준 3595: 맥주 냉장고 (C#)

문제 링크

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

 

 

문제

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

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

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

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

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

 

 

입력

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

 

 

출력

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

 

 

 

통과한 답안

namespace _3595
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());

            // a * b * c = n;
            // 2 * (a * b + b * c + c * a)가 최소

            int minSurface = int.MaxValue;
            Tuple<int, int, int> abc = null;

            for (int a = 1; a <= Math.Ceiling(Math.Pow(n, 1.0 / 3)); a++)
            {
                if (n % a == 0)
                {
                    for (int b = a; b <= Math.Ceiling(Math.Sqrt(n / a)); b++)
                    {
                        if ((n / a) % b == 0)
                        {
                            int c = n / (a * b);
                            int surface = 2 * (a * b + b * c + c * a);
                            if (surface < minSurface)
                            {
                                minSurface = surface;
                                abc = Tuple.Create(a, b, c);
                            }
                        }
                    }
                }
            }

            Console.WriteLine($"{abc.Item1} {abc.Item2} {abc.Item3}");
        }
    }
}

 

n이 주어졌을 때, 부피가 n이면서 겉넓이는 최소인 세 정수를 구하는 문제이다.

정수를 a, b, c라고 했을 때, 부피는 a * b * c이고

겉넓이는 2 * (a * b + b * c + c * a)이므로,

 

이를 for 문을 이용해서 직접 구하는 방식으로 작성하였는데,

한 변의 길이가 될 수 있는 a를 n의 세제곱근까지 구하면서

b는 a의 제곱근까지 구하면서

n을 나눌 수 있는 a와 (n / a)를 나눌 수 있는 b를 구하고

이 a, b, c에 대해서 겉넓이를 구하고 만약 이 겉넓이가 최소라면

a, b, c를 저장하는 방식으로 구현하였다.

 

단순히 a를 n까지 구하는 방식을 이용하였다면 시간 초과가 발생할 수 있는 문제에서

정육면체의 경우가 같은 부피에 대해서 겉넓이는 최소가 되므로

a의 범위를 n의 세제곱근까지로 제한하여 풀이하였다.

 

 

다른 풀이로는 주어진 육면체의 부피 n에 대해서

a * b * c = n 인 경우, 겉넓이 S는 2 * (a * b + b * c + c * a)이므로
이를 최대한 정육면체에 가깝게 만드는 것이 겉넓이가 최소가 되므로

(c = n / ab 이므로, S = 2 * (a * b + n / a + n / b) 이므로 이는 a = b = c인 경우에 최소가 된다)

 

따라서 이 문제를 풀이하는데 있어서

n을 소인수분해한 뒤에 이들로 세 개의 수를 조합해서

이 때의 겉넓이를 최소로 만드는 세 수를 구하는 방법으로 해결할 수 있다.