[백준] 2805 - 나무 자르기 (C++)

https://www.acmicpc.net/problem/2805

상근이가 목재절단기로 나무를 잘라 나무 M미터를 구하려고 한다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 음이 아닌 정수 높이 H를 지정해야 한다. 높이가 H보다 큰 나무는 H 윗 부분이 잘리게 되고, 낮은 나무는 잘리지 않는다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ N ≤ 1,000,000
• 1 ≤ M ≤ 2,000,000,000
• 0 ≤ 나무의 높이 ≤ 1,000,000,000

 

나무의 높이를 매개 변수로 놓고 이분탐색을 진행하면 1,000,000 × log(1,000,000,000)의 시간 안에 해결할 수 있다.

 

left는 0으로, right는 입력받은 나무 높이 중 최댓값으로 둔다. mid 값을 정하고 조건에 맞는 지 확인할 때, 자른 나무 높이의 합이 m보다 크거나 같으면 절단 높이를 높인다. 아닌 경우 절단 높이를 낮추면서 진행하면 된다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. N, M, 나무 높이 정보 입력받기
2. 나무의 높이로 이분탐색 진행하기
   1. l=0으로, r=[나무 높이 중 최댓값]으로 놓기
   2. mid 값에 따라 자른 나무들의 높이의 합을 구하기
   3. 합이 m보다 크거나 같으면 l=mid+1로 놓고 ans 값 갱신하기
   4. 합이 m보다 작으면 r=mid-1로 놓기
3. ans 출력하기

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

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

int n,m,tr[1000001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for (int i=0; i<n; i++) cin >>tr[i];
    sort(tr,tr+n);

    long long int l=0,r=tr[n-1],ans=0;
    while (l<=r) {
        long long int mid = (l+r)/2,sum=0;
        for (int i=0; i<n; i++) {
            sum += (tr[i]-mid>0 ? tr[i]-mid : 0);
        }
        if (sum>=m) {
            l = mid+1;
            ans = max(ans,mid);
        }
        else {
            r = mid-1;
        }
    }
    cout << ans;
}