https://www.acmicpc.net/problem/2805
문제
> 상근이는 나무 M미터가 필요하다.
근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다.
> 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.
> 목재절단기는 다음과 같이 동작한다.
> 먼저, 상근이는 절단기에 높이 H를 지정해야 한다.
> 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다.
> 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다.
> 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다.
> 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자.
> 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다)
> 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.
> 상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다.
> 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.접근
나무의 크기, 가져가야하는 범위가 억단위가 넘어가므로 오버플로우 방지를 위해 longlong형으로 변수들을 사용한다.
나무의 크기가 최대 10억 까진데 절단기에 사용할 수 있는 높이는 양의정수라고 했으므로 나무의 크기가 젤 클때 보다 클 필요는 없으므로(어차피 안잘림) 나무의 크기를 최대값으로 잡고 한다.
이분탐색으로 톱의 크기가 0, 10억 일때 중간값을 구해 나무의 길이를 입력받고 각각 나무를 자른다. 톱보다 작으면 안잘리고 높으면 잘린크기를 다 누적한다.
이 누적값이 원하는 M값 보다 크면 좀 더 톱의 높이를 낮춰도 되니까 다시 범위를 반으로 줄여 탐색하고
M보다 작으면 톱을 더 높게 즉 중간값의 오른쪽값으로 다시 탐색한다. 만약 M과 같으면 원하는 값을 얻은거니까 그대로 그때의 중간값을 출력한다.
문제해결
> 나무의 길이를 입력받을 tree 벡터를 N만큼 크기를 지정해 선언하고, M과 나무의 길이를 입력받아준다.
> 자를 나무를 연산할 메소드를 Tree로 정의하고 인자로 이분탐색 할 것이므로 left, right, 결과로 얻은 중간값을 저장할 rst를 받는다. 다음 재귀에 사용한다.
> 톱의 높이 범위가 역전이 되어 불가능한 높이가 되면 rst를 반환하고 끝낸다. 이 변수엔 재귀를 돌며 담긴 mid값이 들어있다. 이걸 탈출 조건으로 한다.
중간값을 계산하고 잘린 나무의 길이를 누적할 sum변수를 선언한다.
> 반복문으로 각각의 나무를 자른다. 나무가 톱보다 작거나 같으면 안잘리므로 0이 나와 넘어가고 더 크면 나무길이에서 톱 높이를 빼 sum에 누적한다.
> 이 sum이 M보다 작으면 부족하게 챙긴거니까 톱의 범위를 left, mid-1로 더 낮춘다. 그럼 tree - mid 했을 떄 더 큰 값이 누적되므로 M에 근접해간다. 아직 M을 만족하지 못했으므로 rst엔 초기에 들어온 값을 가지고간다.
> M보다 크면 충분히 챙겼으므로 톱의 길이를 더 높여 조금만 잘라준다. 그래서 범위를 mid+1, right로 재설정하고 일단 M을 만족했으니 rst에 mid값을 넣고 재귀한다.
> 만약 M값과 같다면 최적의 높이를찾은것이므로 바로 mid를 반환한다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
long long Max = 1000000000;
long long N, M;
vector<long long> tree;
long long Tree(long long left, long long right, long long rst)
{
if (left > right) return rst;
long long mid = (left + right) / 2;
long long sum = 0;
for (int i = 0; i < N; i++)
{
if (tree[i] <= mid) continue;
sum += (tree[i] - mid);
}
if (sum < M) return Tree(left, mid - 1, rst);
if (sum > M) return Tree(mid + 1, right, mid);
if (sum == M) return mid;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M;
tree.resize(N);
for (int i = 0; i < N; i++) cin >> tree[i];
cout << Tree(0, Max, Max) << '\n';
}
후기
전에 게임 문제로 승률의 변화가 일어나는 게임 수 구하는 문제를 풀어봤어서 접근이 생각보다 쉬웠다. 그래도 나무 값과 톱 높이의 관계에서 헷갈릴 여지가 다분했지만 하나씩 써가며 했다. 원트에 맞아서 좋다.
