백준 1166번 [선물](C++) -yes6686- 티스토리

백준 문제 풀이: 1166 (선물)

---

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

문제 설명:

n개의 정육면체 선물을 상자(l × w × h)에 담으려고 합니다. 선물은 모두 같은 크기로 만들어야 하며, 가능한 가장 큰 선물의 한 변의 길이를 구하는 문제입니다. 길이는 소수점 아래 10자리까지 정확해야 합니다.

---

문제 해결 코드

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    // 입력 받기
    double n, l, w, h;
    cin >> n >> l >> w >> h;

    // 이분 탐색 초기화
    double s = 0; // 가능한 최소 길이
    double e = min({l, w, h}); // 가능한 최대 길이
    double ans = 0;

    // 이분 탐색 반복
    for (int cnt = 0; cnt < 100; cnt++) { // 최대 100번 반복
        double mid = (s + e) / 2; // 중간값
        long long int a = floor(l / mid) * floor(w / mid) * floor(h / mid); // mid 크기로 가능한 정육면체 개수

        if (n <= a) {
            ans = mid; // 가능한 경우, 정답 갱신
            s = mid;   // 더 큰 값을 탐색
        } else {
            e = mid;   // 더 작은 값을 탐색
        }
    }

    // 결과 출력
    cout << fixed;
    cout.precision(10);
    cout << ans << '\n';

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 핵심 알고리즘: 이분 탐색을 사용해 선물의 한 변의 최대 길이를 찾습니다. 가능한 최대 길이는 상자의 최소 치수(l, w, h)로 제한됩니다.
• 구현 세부사항:
  • floor(l / mid): mid 크기의 선물이 가로 방향으로 몇 개 들어갈 수 있는지를 계산합니다.
  • floor(l / mid) * floor(w / mid) * floor(h / mid): mid 크기의 선물을 상자에 몇 개 담을 수 있는지 계산합니다.
  • 이분 탐색은 100번 반복하여 정확도를 높입니다.
• 시간 복잡도 분석:
  • 이분 탐색은 O(log k), 여기서 k는 가능한 최대 길이와 최소 길이의 차이입니다.
  • 각 단계에서 가능한 정육면체의 개수를 계산하는 연산은 O(1)입니다.
  • 전체 시간 복잡도는 O(log k)입니다.

---

결과

주어진 상자 크기와 선물 개수에 따라, 가장 큰 크기의 선물 한 변의 길이를 정확히 계산합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!