[C]백준_3595 : 맥주 냉장고

Alal11·2023년 3월 19일

출처

https://www.acmicpc.net/problem/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 ≤ 106)

출력

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

예제 입출력

알고리즘 분류

수학
브루트포스 알고리즘

➡️문제 분석

a x b x c 크기의 냉장고

1 x 1 x 1 크기의 맥주 박스

n개의 맥주 박스가 있다.

냉장고의 용량이 12라고 하면,

a x b x c = 12가 되어야 한다.

a, b, c가 3, 2, 2 라고 하면,

12 % a 는 무조건 0이 되어야 하고, 12 / a == b * c가 된다.
12 % (a*b)는 무조건 0이 되어야 하고, 12 / (a*b) == c가 된다.

➡️코드(⭕)

#include <stdio.h>

int main()
{
	int n;
	int min = 100000000;
	int a, b, c;
	int area;

	scanf("%d", &n);

	for (int i = 1; i <= n; i++)		// i는 1부터 n까지 반복
	{
		if (n % i == 0)					// n % i가 0이 되는 i 값만 가능
		{
			for (int j = 1; j <= n / i; j++)		// j는 1부터 n/i 까지 반복
			{
				if (n % (i * j) == 0)				// i와 j를 곱한 값을 n으로 나눈 나머지가 0이 되는 경우
				{
					for (int k = 1; k <= n / (i * j); k++)		// k는 1부터 n을 i*j로 나눈 몫까지 반복
					{
						// i * j * k는 n이 되어야 함
						if (i * j * k == n)
						{
							area = (i * j + j * k + i * k) * 2;		// 직육면체 겉넓이 구하는 공식

							// 겉넓이가 가장 작은 값을 min에 넣어주고 그때의 가로, 세로, 높이를 구함
							if (area < min)
							{
								min = area;
								a = i;
								b = j;
								c = k;
							}
						}
					}
				}
			}
		}
	}
	printf("%d %d %d", a, b, c);		// 가로, 세로, 높이 출력
}