[BOJ 1166] 선물

 

 

 

 

문제 링크

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

1166번: 선물

---

아이디어

이분 탐색을 통해, L*W*H의 박스안에 A*A*A의 박스가 N개 이상 들어가도록하는 A의 최대값을 찾는다.

 

---

주의할 점

• L, W, H는 최대 1e9이기 때문에 num의 최대값은 1e27라고 생각할 수 있다.
  이 때, 1e27은 8byte의 long long int로도 표현할 수 없는 큰 수이다.
  하지만 N=1e9일 때, mid의 최소값은 1e3이며 따라서 num의 최대값은 1e18로 long long int로 커버 가능하다.

 

• 이분 탐색의 반복문을 while (hi - lo > eps) 로 할 경우,
  hi, lo의 자료형이 double이라면 IEEE 754의 한계 때문인지 무한루프에 빠지게 된다.
  따라서 long double로 해결하거나 아래와 같이 임의로 충분한 수의 반목문을 돌려주어 해결하자.

 

---

소스코드

#include <cstdio>
#include <algorithm>

using namespace std;

int n, a[3];
long long num;
double lo = 0, hi = 2e10, mid;

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < 3; ++i)
        scanf("%d", a + i);

    for (int i = 0; i < 30000; ++i) {
        num = 1;
        mid = (lo + hi) / 2;
        for (int i = 0; i < 3; ++i) {
            num *= (long long)(a[i] / mid);
        }
        if (num < n) {
            hi = mid;
        }
        else {
            lo = mid;
        }

    }
    printf("%.10lf\n", lo);
  	return 0;
}

 

 

 

 

공부한 것을 정리하기 위한 기록입니다.

상냥한 피드백은 감사히 받겠습니다.