[C++] 선물 (백준 1166번)

https://www.acmicpc.net/problem/1166

 

#include <iostream>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, l, w, h;
    cin >> n >> l >> w >> h;

    ld li = 0;
    ld ri = l + 1;
    for (int i = 0; i < 100; i++) {
        ld mi = (li + ri) / 2;
        ll tmp = ((ll) (l / mi) * (ll) (w / mi) * (ll) (h / mi));
        if (tmp < n) ri = mi;
        else li = mi;
    }

    cout << fixed;
    cout.precision(10);
    cout << li << '\n';
}

실수 이분 탐색 문제는 처음 풀어봤다. (정답)

우선, 오차는 10^(-9)까지 허용한다고 하니 cout << fixed; cout.precision(10); 를 적어준다.

li, ri, mi 전부 실수로 정의하되, 이분 탐색 계산할 때는 정수로 계산한다. 그리고 while (li < ri) 대신 for (int i = 0; i < 100; i++) 를 써서 탐색 횟수에 제한을 주어야 한다. (참고로 탐색 횟수를 50까지로만 하니까 틀렸습니다가 떴다.) 업데이트 해줄 때는 각각 li = mi, ri = mi 로 업데이트 한다.