[SWEA] 1491. 원재의 벽 꾸미기

문제

새 집으로 이사를 온 원재는 밋밋한 방을 꾸미기 위해 1 X 1타일 N개를 이용해 R X C 크기의 직사각형 인테리어를 하나 만들어 벽면을 꾸미려고 한다.

그런데, 원재의 방은 정사각형 형태이기 때문에 만드는 직사각형 인테리어를 최대한 정사각형에 가깝게 만들면서, 최대한 많은 타일을 사용하려고 한다.

두 조건을 모두 만족하기 어렵다고 판단한 원재는 이 두 조건에 대해 가중치 A, B를 가지고 나름의 식을 도출해냈다.

A X lR – Cl + B X (N - R X C)

원재는 위의 값을 최소화하려고 한다. 최소화된 이 값을 출력하는 프로그램을 작성하라.

 

풀이방법

R X C <= N을 만족할 때,

 

A X lR – Cl + B X (N - R X C)의 최소값을 찾는다.

 

소스코드

package samsung;

import java.util.*;

public class s_1491 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			long n = sc.nextLong();
			long a = sc.nextLong();
			long b = sc.nextLong();
			long min = -1;
			for(int i = 1; i <= n; i++) {
				int j = 1;
				while(true) {
					if(i * j > n)
						break;
					long sum = a * Math.abs(i - j) + b * (n - i * j);
					if(min == -1)
						min = sum;
					else {
						min = Math.min(min, sum);
					}
					j++;
				}
			}
			System.out.println("#" + t + " " + min);
		}
	}
}