[알고리즘] 백준 1166번: 선물 (C++)

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

1166번: 선물

이번 문제는 간단히 이분 탐색이라기보다 부가적인 요소로 신경 써야 할 것이 많은 문제였다.

1. 자료형
2. while을 이용한 이분 탐색이 아닌 for문을 이용해야 함 (혹은 double이 아닌 long double로 선언)
3. 출력은 실수형

---

솔루션

(+참고 https://vision-ary.tistory.com/2)

1) 자료형

l, w, h가 주어졌을 때 최댓값이 1e27이 되어 long long을 초과한다.

즉석으로 l * w * h로 들어갈 수 있는 부피를 구하지 않고, 각 길이(l, w, h)에 주어진 mid를 나눈 뒤 곱하여서 부피가 아닌 '들어갈 수 있는 개수'를 바로 구해주었다.

 

2) while문 오류

while로 코드를 돌렸을 때 double의 특성 때문에 오류가 나는 듯하다. 특정한 이유는 알아내지 못했다.

while(low <= high)의 조건 low <= high에서 계속 low가 high가 작은 경우도 있어서 오류가 난다고 한다.

그래서 무한 루프가 난다고 한다.

for문을 일정 수치 (10000)만큼 돌려 이분 탐색을 해주었다.

(https://vision-ary.tistory.com/2)

 

3) 출력

출력은 상대 오차를 줄여주기 위해 소수점 아래 16자리만큼 출력해주었다.

 

[AC 코드]

#include <iostream>
#include <cmath>
#define ll long long
using namespace std;

ll n, l, w, h;

bool judge(double mid) {
	if ((ll)(l / mid) * (ll)(w / mid) * (ll)(h / mid) >= n) {
		return 1;
	}
	else {
		return 0;
	}
}

int main() {
	cin >> n >> l >> w >> h;

	double low = 0;
	double high = 1000000000;
	double result = 0;

	for (int i = 0; i < 10000; i++) {
		double mid = (low + high) / 2;
		if (judge(mid)) {
			low = mid;
		}
		else {
			high = mid;
		}
	}

	cout.precision(16);
	cout << fixed;
	cout << low;
	return 0;
}