[백준] 3595번: 맥주 냉장고

문제

백준 - 3595번: 맥주 냉장고

분석

냉장고 용량 n (axbxc=n)이 주어졌을 때, 겉넓이가 가장 작은 경우의 a, b, c를 구하는 문제이다.

두 번의 for문을 거치면서 n을 나눴을 때 나머지가 0이 된다면 a x b x c = n을 만족하는 경우이고 모든 가능한 경우를 따지면서 겉넓이가 가장 작았을 때의 a, b, c를 구하면 된다. 이때 실제 겉넓이를 원하는 것이 아니기 때문에 굳이 x2를 안해도 된다.

바깥 for문은 n만큼 안쪽 for문은 약수인 경우만 돌아가기 때문에 nlog(n) 정도의 시간복잡도이다.

코드

해결언어 : Java

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static int N, mn;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		mn = Integer.MAX_VALUE;
		int a = 0, b = 0, c = 0;
		for (int i = 1; i <= N; i++) {
			if (N % i != 0)
				continue;
			int num = N / i;
			for (int j = 1; j <= num; j++) {
				if (num % j != 0)
					continue;
				int k = num / j;
				int val = i * j + j * k + k * i;
				if (val < mn) {
					mn = val;
					a = i;
					b = j;
					c = k;
				}
			}
		}
		System.out.println(a + " " + b + " " + c);
		br.close();
	}

}