[백준 알고리즘] 백준 1166번 선물 자바(Java)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 1166번 선물 자바(Java)

1) 문제번호 : 1166번

 

2) 문제 출처

www.acmicpc.net/problem/1166

1166번: 선물

 

2. 문제

오민식은 아이들에게 선물할 모두 같은 크기의 작은 박스를 N개 가지고 있다. 모든 박스는 A * A * A크기의 정육면체이다. 오민식은 이 작은 박스를 L * W * H 크기의 큰 직육면체 박스에 넣으려고 한다. 모든 작은 박스는 큰 박스 안에 있어야 하고, 작은 박스의 변은 큰 박스의 변과 평행해야 한다.

N, L, W, H가 주어질 때, A의 최댓값을 찾는 프로그램을 작성하시오.

 

3. 제약사항

- 

4. 입력

첫째 줄에 N L W H가 주어진다. 모든 값은 1,000,000,000보다 작거나 같은 자연수이다.

 

5. 출력

첫째 줄에 문제의 정답을 출력한다. 절대/상대 오차는 10-9까지 허용한다.

 

6. 풀이

- 입력값의 범위 때문에 시간이 걸린 문제.

- 10억이 넘어가는 값을 입력받기 때문에, long으로 받고, BinarySearch를 통해 풀면 된다.

 

7. 소스 코드

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long N = sc.nextInt(); // 상자 갯수
		long L = sc.nextInt(); // 가로
		long W = sc.nextInt(); // 세로
		long H = sc.nextInt(); // 높이
		
		double low = 0;
		double high;
		
		high = Math.max(L, Math.max(W, H));
		for(int i=0;i<10000;i++) {
			double mid = (low + high)/2;
			if((long)(L/mid)*(long)(W/mid)*(long)(H/mid)>=N) low = mid;
			else high = mid;
		}
		System.out.println(low);
	}
}

---