이진 탐색을 이용한 접근 방법
이 문제는 가장 큰 나무 조각의 길이를 찾는 것이 목표입니다. 먼저, 모든 가능한 길이를 순서대로 시도하는 브루트 포스 방식으로 접근할 수 있지만, 이 방법은 시간 초과가 발생할 가능성이 높습니다. 따라서, 더 효율적인 방법을 사용해야 합니다.
주요 아이디어
이진 탐색을 이용하면, 불필요한 길이 범위를 제거하여 검색 공간을 줄일 수 있습니다. 이진 탐색을 사용하려면, 특정 길이로 나무를 자른 결과가 조건을 만족하는지 여부를 판단하는 함수가 필요합니다.
다음은 해당 함수의 예시입니다:
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; // 결과 출력
}
요약
이진 탐색을 사용하여 나무를 자르는 문제를 해결할 때, 다음 두 가지 조건이 필요합니다:
- 가능한 답이 상한과 하한이 있어야 합니다.
- 특정 길이로 나무를 자른 결과가 조건을 만족하는지 여부를 판단할 수 있어야 합니다.
이진 탐색은 일반적인 열거법에 비해 효율적으로 검색 범위를 줄여줍니다. 이러한 방법은 다른 유사한 문제에도 적용할 수 있습니다. 예를 들어, "돌 던지기" 문제와 같은 다른 문제에서도 유사한 접근 방식을 사용할 수 있습니다.