(C++) - 백준(BOJ) 1166번 : 선물 답

www.acmicpc.net/problem/1166

1166번: 선물

간단한 이분탐색이었으나.. 자료형과 시간초과, 출력을 신경써야되는 그런 문제였습니다.

풀이방법

 찾으려는 정육면체 박스의 한변 길이를 mid로 하여 이분탐색을 시행합니다.

 1. 이분탐색 로직

  1-1. (가로/mid * 세로/mid * 높이/mid)의 값이 n미만이면 박스의 길이를 줄여야 합니다. 곱하게 되므로 int 범위를 초과할 수 있기 때문에 각 항을 long long형으로 변환해줘야합니다.

  1-2. 반대라면 박스의 길이를 늘일 수 있습니다.

 

2. 출력 : 1-2의 경우일때의 left값이 곧 최대의 박스 길이입니다. 출력시 상대오차를 고려해 출력해줍니다.

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    int n,l,w,h;
    double left = 0, right= 1000000000, mid;
    cin >> n >> l >> w >> h;
    for(int i = 0; i < 10000; i++){
        mid = (left+right)/2;
        if(((ll)(l/mid))*((ll)(w/mid))*((ll)(h/mid)) < n) right=mid;
		else left=mid;
    }
    printf("%.10lf",left);
}