[백준/C++] 1166번 선물 풀이 (탐색 횟수 설명)

문제 해석

---

문제 풀이

---

문제 알고리즘 선택

• 우선 최대 박스의 크기와 갯수가 모두 10억개 이상이니 int 범위로는 overflow가 날 수 있다.
• 단순 수학 문제로 생각했으나 정수가 아닌 실수 정답을 가지고 있어 추가적인 방법을 고민
• 이분 탐색을 생각했고, 제출했으나 소수점 자리에서 무한 루프가 발생
• 최대 실행 횟수를 고려하게 됨

실행 횟수 풀이 과정

1. 정답은 1~10⁹ 까지 값을 가지고 소수점 역시 최대 9자리까지이므로 이분 탐색으로 log₂(10¹⁸)이다.
2. 대략 18/0.3xx으로  59.x회
3. 최대 탐색횟수는 60으로 제한하고 실행하면 된다! (계산 어렵고 귀찮으면 100정도 잡아도 될 것 같다)

 

코   드

---

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long int N, L, W, H;
    cin >> N >> L >> W >> H;
    long double low = 0.0, mid, high = 1000000000.0;

    mid = (low + high) / 2.0;
    int cnt = 60;
    while(cnt--) {
        if ((long long int)(L / mid) * (long long int)(W / mid) * (long long int)(H / mid) >= N) {
            low = mid;
        } else {
            high = mid;
        }
        mid = (low + high) / 2.0;
    }
    cout << fixed;
    cout.precision(9);
    cout << low;
}

 

느낀점: 로직은 크게 어렵지 않으나 이분탐색 문제임을 알아내는 것과 최대 실행 횟수를 알아내는 것이 관건 이었던 것 같다.

날짜: 2024.09.12 [이분탐색]

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