[SWEA] - 1491. 원재의 벽 꾸미기 (D3)

[문제]

새 집으로 이사를 온 원재는 밋밋한 방을 꾸미기 위해 1 X 1타일 N개를 이용해 R X C 크기의 직사각형 인테리어를 하나 만들어 벽면을 꾸미려고 한다.
그런데, 원재의 방은 정사각형 형태이기 때문에 만드는 직사각형 인테리어를 최대한 정사각형에 가깝게 만들면서, 최대한 많은 타일을 사용하려고 한다.
두 조건을 모두 만족하기 어렵다고 판단한 원재는 이 두 조건에 대해 가중치 A, B를 가지고 나름의 식을 도출해냈다.

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

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

[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 세 정수 N, A, B(1 ≤ N, A, B ≤ 105)가 공백으로 구분되어 주어진다.

[출력]
각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 답을 출력한다.

문제 풀기

1491. 원재의 벽 꾸미기

 

---

[풀이]

• R X C 크기의 인테리어를 N개의 타일로 만들어야 하므로 (N - R × C) 는 0보다 크거나 같아야한다.

import java.util.Scanner;

class Solution {
	public static void main(String[] args) throws Exception {		
		Scanner sc = new Scanner(System.in);
		
		int t = sc.nextInt();
		
		for(int tc=1; tc<=t; tc++) {
			long n = sc.nextInt();
			long a = sc.nextInt();
			long b = sc.nextInt();
			
			long min = Long.MAX_VALUE;
			long result;
			
			for(long c=1; c<=n/2; c++) {
				for(long r=c; r*c<=n; r++) {
					result = a * (r - c) + b * (n - r * c);
					if(result<min) min = result;
				}
			}
			
			System.out.format("#%d %d\n", tc, min);
		}
	}
}