[백준 2805] 나무 자르기

[백준 2805] 나무 자르기

문제 출처 : https://www.acmicpc.net/problem/2805

문제상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기을 이용해서 나무를 구할것이다.

목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다)

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이 때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최대값을 구하는 프로그램을 작성하시오.

입력첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M을 넘기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

출력적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최대값을 출력한다.


예제 입력

4 7
20 15 10 17

예제 출력

15

• 문제 이해하기

첫번째 줄 입력은 '나무의 수'와 '집으로 가져갈 나무 길이의 수'다.

두번째 줄 입력은, 입력한 나무의 수만큼 나무마다 각각의 길이를 입력해주면 된다.

따라서 현재 문제에 나온 예제는 나무 4그루를 가지고 길이가 7인 나무를 가져갈 것이라는 뜻이다.

4그루의 길이는 각각 20, 15, 10, 17로 주어진 상태다.

상근이는 높이 H를 지정해서 나무를 절단하고, 잘린 길이의 나무를 가져간다고 한다. 따라서 각 나무에서 잘린 길이의 합이 7이 되는 높이 H를 찾아야 한다.

지금처럼 H를 15로 자르면 나무의 높이는 15, 15, 10, 15가 될 것이고 잘린 나무는 5와 2로 총 7이 된다.

이처럼 내가 처음에 지정한 길이에 가장 가까운 길이를 얻을 수 있는 H를 찾도록 만들어야 한다.

• 계획 및 문제 해결

정답 후보를 이미 입력한 후에 과정을 찾아야 하는 문제다. 따라서 이분 탐색을 이용해야 한다.

유추하는 과정을 통해 일치하거나 가장 근접한 정답 값을 찾아야 한다.

이분 탐색

정렬되어있는 리스트가 있을 때, 가운데 값과 비교해나가면서 가능한 정답의 범위를 절반으로 줄여나가며 어떤 수가 존재하는 지, 존재하지 않는 지 찾는 알고리즘
문제에 주어지는 기준 점(X)를 통해 가능성 여부를 따져서 정답을 찾아낸다.


따라서 우리는 주어진 나무 길이에서 가장 작은 값(0)과 가장 큰 값(20)을 가지고, 중간 값을 통해 가능 여부를 확인하면서 정답의 범위를 좁혀나갈 것이다.
좁혀나가는 과정에서 잘린 길이의 합이 입력한 M에 가장 근접했을 때가 우리가 찾는 높이의 최대값이 될 것이다.

우선 tree의 길이를 저장할 배열을 만들자. 100만까지 가능하다 했으므로 변수의 크기는 long long으로 설정한다.

long long tree[1000001]; // 100만 크기의 tree 배열 선언

메인 함수에서 우선 정의가 필요한 변수는 다음과 같다.

long long N; // 나무 수
long long M; // 집으로 가져갈 나무 길이
long long max = 0; // 최대 값 저장할 max 선언
long long left, right; // 가능한 값을 찾는 과정에 활용할 변수 선언

left와 right라는 변수는 이분 탐색을 통한 값을 찾기 위해 만들었다.

cin >> N >> M;
 
for (int i = 0; i < N; i++) {
    cin >> tree[i];
 
    if (max < tree[i]) // tree에서 가장 큰 값 max에 저장
        max = tree[i];
}

우선, 입력과정을 시작한다. 나무 수 N과 가져갈 나무 길이 값 M을 입력한다.

for문을 통해 N만큼 반복해서 tree[i]에 각 나무의 길이를 입력한다.

이때 입력한 나무 길이 중 가장 큰 값을 max에 저장한 상태다. 이 값을 right 변수에 넣을 것이다.

left = 0; // 왼쪽 끝은 0
right = max; // 오른쪽 끝은 max 값

left는 0으로, right값을 나무의 최대 길이로 저장했다.

중간값에 해당하는 mid를 만들어주는데, 이 mid 값은 우리가 나무를 자를 높이 H에 해당한다. 자르고 남은 길이의 합을 통해 M과 비교할 것이다.

    long long answer = 0; // 정답을 저장할 변수 선언
 
    while (left <= right) { // left가 right 이하일 때 loop
        long long mid = (left + right) / 2; // 중간 값
        long long sum = 0; // 자르고 남은 길이 합 저장할 변수 선언
 
        for (int i = 0; i < N; i++) {
            if (mid < tree[i])
                sum += tree[i] - mid; // sum에 나무 자르고 남은 길이 더하기
        }
 
        if (sum >= M) { // 만약 sum이 집으로 가져갈 나무 길이 이상이면?
            if (answer < mid)
                answer = mid;
            left = mid + 1;
        }
        else // sum이 M보다 작으면
            right = mid - 1;
    }

sum에는 mid를 이용해서 자르고 남은 길이의 합이 저장된다.

이제 이 sum이 M보다 크거나 같을 때와 작을 때로 조건문을 통해 나눠야 한다.

sum이 M보다 크거나 같으면 H를 증가시켜야 하고, M보다 작으면 H를 감소시켜야 한다.

이 과정을 통해 left값이 right보다 커지면 answer에 저장된 mid 값이 답이 될 것이다.

• 전체 소스 코드

#include <iostream>
 
using namespace std;
 
long long tree[1000001]; // 100만 크기의 tree 배열 선언
 
int main() {
 
    long long N; // 나무 수
    long long M; // 집으로 가져갈 나무 길이
    long long max = 0; // 최대 값 저장할 max 선언
    long long left, right; // 가능한 값을 찾는 과정에 활용할 변수 선언
 
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        cin >> tree[i];
 
        if (max < tree[i]) // tree에서 가장 큰 값 max에 저장
            max = tree[i];
    }
 
    left = 0; // 왼쪽 끝은 0
    right = max; // 오른쪽 끝은 max 값
 
    long long answer = 0; // 정답을 저장할 변수 선언
 
    while (left <= right) { // left가 right 이하일 때 loop
        long long mid = (left + right) / 2; // 중간 값
        long long sum = 0; // 자르고 남은 길이 합 저장할 변수 선언
 
        for (int i = 0; i < N; i++) {
            if (mid < tree[i])
                sum += tree[i] - mid; // sum에 나무 자르고 남은 길이 더하기
        }
 
        if (sum >= M) { // 만약 sum이 집으로 가져갈 나무 길이 이상이면?
            if (answer < mid)
                answer = mid;
            left = mid + 1;
        }
        else // sum이 M보다 작으면
            right = mid - 1;
    }
 
 
    cout << answer << endl;
 
}