이진 탐색을 이용한 나무 자르기 문제 해결

이진 탐색을 이용한 접근 방법

이 문제는 가장 큰 나무 조각의 길이를 찾는 것이 목표입니다. 먼저, 모든 가능한 길이를 순서대로 시도하는 브루트 포스 방식으로 접근할 수 있지만, 이 방법은 시간 초과가 발생할 가능성이 높습니다. 따라서, 더 효율적인 방법을 사용해야 합니다.

주요 아이디어

이진 탐색을 이용하면, 불필요한 길이 범위를 제거하여 검색 공간을 줄일 수 있습니다. 이진 탐색을 사용하려면, 특정 길이로 나무를 자른 결과가 조건을 만족하는지 여부를 판단하는 함수가 필요합니다.

다음은 해당 함수의 예시입니다:

bool isPossible(long long length) {
    int count = 0;
    for (int i = 0; i < n; ++i) {
        count += wood[i] / length; // 현재 길이로 나무를 자른 조각 수를 계산
    }
    return count >= k; // 조건을 만족하는지 확인
}

이 함수는 주어진 길이 length로 나무를 자른 후, 얻은 조각 수가 k 이상인지 확인합니다. 만족하면 true, 그렇지 않으면 false를 반환합니다.

전체 코드

아래는 전체 코드입니다. 입력과 출력, 그리고 이진 탐색 로직을 포함하고 있습니다.

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

long long n, k;
long long wood[100005];

bool isPossible(long long length) {
    int count = 0;
    for (int i = 0; i < n; ++i) {
        count += wood[i] / length; // 현재 길이로 나무를 자른 조각 수를 계산
    }
    return count >= k; // 조건을 만족하는지 확인
}

int main() {
    cin >> n >> k;
    long long totalLength = 0;
    for (long long i = 0; i < n; ++i) {
        cin >> wood[i];
        totalLength += wood[i]; // 총 길이 계산
    }

    if (totalLength < k) {
        cout << 0; // 총 길이가 k보다 작으면 0 출력
        return 0;
    }

    sort(wood, wood + n); // 나무 길이 정렬
    long long left = 1, right = wood[n - 1]; // 초기 범위 설정
    long long result = 0; // 결과 저장 변수

    while (left <= right) {
        long long mid = (left + right) / 2;
        if (isPossible(mid)) {
            result = mid; // 현재 가능한 길이 저장
            left = mid + 1; // 더 큰 길이를 시도
        } else {
            right = mid - 1; // 더 작은 길이를 시도
        }
    }

    cout << result; // 결과 출력
}

요약

이진 탐색을 사용하여 나무를 자르는 문제를 해결할 때, 다음 두 가지 조건이 필요합니다:

  • 가능한 답이 상한과 하한이 있어야 합니다.
  • 특정 길이로 나무를 자른 결과가 조건을 만족하는지 여부를 판단할 수 있어야 합니다.

이진 탐색은 일반적인 열거법에 비해 효율적으로 검색 범위를 줄여줍니다. 이러한 방법은 다른 유사한 문제에도 적용할 수 있습니다. 예를 들어, "돌 던지기" 문제와 같은 다른 문제에서도 유사한 접근 방식을 사용할 수 있습니다.

태그: 이진 탐색 C++ 알고리즘 나무 자르기 구간 축소

10월 14일 00:17에 게시됨