문제 출처
https://www.acmicpc.net/problem/2805
2805번: 나무 자르기
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보
www.acmicpc.net
문제
접근 방법
ㆍ적어도 M미터의 나무를 가져갈 수 있는 높이의 최댓값을 찾아야 한다.
ㆍ어쨌든 값을 찾는 방식의 문제이기 때문에 '탐색'을 이용하는 것이 좋겠다는 생각을 했다.
ㆍN은 100만까지 가능하고, M은 20억까지 가능하기 때문에, 굉장히 큰 수이므로, 선형 탐색으로 구현하게 되면 시간 초과 가 날 것이라고 생각을 했다.
ㆍ그래서 이분 탐색(Binary Search)를 사용하기로 했다. (이분 탐색을 위해서는 이전에 정렬이 되어야 한다.)
ㆍ첫 번째 예제를 예로 들어 진행 과정을 살펴보자.
- N = 4, M = 7인 상황이다.
- 20 15 10 17이 입력되면, 이분 탐색을 위해서 정렬이 되어야 한다.
sort() 함수를 통해 오름차순으로 정렬을 해준다.
- 그러면, 10 15 17 20 으로 나열된 상황이다. (나무의 높이들)
- 이분 탐색 함수 (BinarySearch)
-> 맨 처음 left와 right를 설정해주어야 한다.
-> left = 0, right = v[n - 1]로 설정해준다.
(주의해야 할 점)
left = v[0] 으로 설정하는 것이 아니라, left = 0으로 설정해주어야 한다.
만약에, left = v[0]으로 설정한다면, left = 10이 되고, right = 20인 상황이다.
그러면, 우리가 궁극적으로 찾아야 할 높이는 10과 20 사이에서만 찾을 수 있게 된다.
하지만, 만약에 적어도 30미터를 가져오고 싶다고 해보자.
그렇다면, 우리는 절단기의 높이를 8미터로 설정해주어야 한다.
( (10 - 8) + (15 - 8) + (17 - 8) + (20 - 8) = 2 + 7 + 9 + 12 = 30 )
8은 10과 20 사이에 존재하지 않기 때문에, 원하는 값을 찾을 수 없게 되는 것이다.
그래서, 다른 아이디어가 필요하다.
-> left = 0, right = v[n - 1]로 설정해준다.
즉, 0부터 v[n-1] 까지 모든 수가 나열된 배열을 생각하는 것이다.
예제1을 예로 들면, 0부터 20까지의 배열을 생각하는 것이다.
0, 1, 2, 3, ... , 9, 10, 11, ... , 18, 19, 20
위의 배열을 기반으로 이분 탐색을 실행한다고 생각하자.
코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int BinarySearch(vector <int> v, int n, int m) {
// left가 v[0]이 아님을 주의하자
// v[0]보다 작은 값으로 나무 자르기도 가능함을 생각하자
int left = 0;
int right = v[n - 1];
// left부터 right까지 모든 숫자가 나열된 배열을 생각하자
// left = 0, right = 20이라면 0, 1, 2, ..., 19, 20 배열을 생각하자
// 이 배열에서 이분 탐색을 하는 것이라고 생각하자
int diff;
int max = 0; // 적어도 m미터의 나무를 가져가도록 하기 위한 높이의 최댓값
while (left <= right) {
long long sum = 0; // 자른 나무 길이의 총합
int mid = (left + right) / 2;
for (int i = 0; i < n; i++) { // n은 나무의 개수
if (v[i] > mid) {
diff = v[i] - mid;
sum += diff;
}
}
if (sum >= m) {
left = mid + 1;
max = mid;
}
else
right = mid - 1;
}
return max;
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int N, M, high;
long long ans;
vector <int> v;
cin >> N >> M;
for (int i = 0; i < N; i++) {
cin >> high;
v.push_back(high);
}
sort(v.begin(), v.end());
ans = BinarySearch(v, N, M);
cout << ans;
return 0;
}주의해야 할 점
1. left = v[0] 이 아니라, left = 0으로 설정해준다.
2. BinarySearch() 함수 내의 while문의 조건을 left < right가 아니라, left <= right 으로 설정해준다.
-> left < right 일 경우의 반례
(입력)
2 11
10 10
(풀이)
절단기 높이가 5라면 (10 - 5) + (10 - 5) = 10이 되고, 높이가 4라면 (10 - 4) + (10 - 4) = 12가 된다.
딱 11미터를 가져올 수는 없지만, 적어도 11미터를 가져오기 위해서는 절단기 높이는 4가 되어야 한다.
left = 0, right = 10인 상황, mid = 5가 됨 (m = 11)
sum = (10 - 5) + (10 - 5) = 10이 됨
sum < m (10 < 11)이므로, right = mid - 1 = 5 - 1 = 4가 됨
left = 0, right = 4이므로, mid = 2가 됨
sum = (10 - 2) + (10 - 2) = 16이 됨
sum > m (16 > 11)이므로, left = mid + 1 = 2 + 1 = 3이 되고, max = mid = 2가 됨
left = 3, right = 4이므로, mid = 3이 됨
sum = (10 - 3) + (10 - 3) = 14가 됨
sum > m (14 > 11)이므로, left = mid + 1 = 3 + 1 = 4가 되고, max = mid = 3이 됨
left = 4, right = 4이므로, left < right 조건을 만족하지 못하기 때문에, while문을 빠져나오게 됨
그러면, max = 3을 return하게 된다.
그러나, 우리가 원하는 답은 max = 4인 경우이다.
여기서, left <= right라고 해보자
left = 4, right = 4이므로, mid = 4가 됨
sum = (10 - 4) + (10 - 4) = 12가 됨
sum > m (12 > 11) 이므로, left = mid + 1 = 4 + 1 = 5가 되고, max = 4가 됨
left = 5, right = 4이므로, left <= right 조건을 만족하지 못하기 때문에, while문을 빠져나오게 됨
그러면, max = 4를 return하게 되고, 우리가 원했던 답이다.
3. 나무의 길이는 20억까지 가능하기 때문에, 나무의 길이를 다루는 변수는 int로 선언해도 된다.
그러나, 나무의 길이를 더하는 경우 (나무의 길이의 합을 구하는 경우) 에는 나무의 길이의 합이 20억을 넘는 경우가 발 생한다. 따라서, 나무의 길이의 합을 다루는 변수는 long long으로 선언해야 한다.
느낀 점
굉장히 오랜 시간에 걸쳐서 푼 문제이다.
이분 탐색의 기본적인 형태는 간단하기 때문에, 이를 응용한 문제 또한 쉽게 풀 수 있을 것이라고 생각했다.
그러나, 생각보다 아이디어를 떠올리기 쉽지 않았다.
이분 탐색 관련한 문제를 많이 풀어보면서 감을 익히는 것이 중요할 것 같다.
