Written by JS970
on February 4, 2023

2805 - 나무 자르기

난이도: 실버 2
날짜: 2023년 2월 4일
상태: Correct/Retry
추가 검토 여부: Yes

solution

문제를 보자마자 1654번 문제와 마찬가지로 이분 탐색을 이용하여 푸는 문제임을 알았다… 그러나…
이분 탐색을 제대로 이해하지 못한 채 priority_queue를 사용하여 처음에 시간초과가 발생하여 오답
이분 탐색의 범위를 잘못 설정한 채 계속 오답
- 시작점과 끝점 설정을 잘못 설정하였다. 그러나 이분 탐색 분기점 코드의 문제로 의심하고 계속 헛짓거리함
- 처음 max, min을 설정할 때 min값을 입력값 중 최솟값으로 설정하였다 → 이러면 반례가 너무 많다. 하지만 알아차리지 못했다.
- 대표적으로 모든 나무의 크기가 같은 경우 오답을 출력한다.
오답의 원인은 아니었지만 잘린 나무 길이를 더했을 때 일시적으로 int범위를 벗어나므로 오버플로우에 의한 에러가 발생할 수 있음에 주의해야 한다.

code

#include <iostream>

using namespace std;

int main()
{
    int N;
    int M;
    cin >> N;
    cin >> M;
    int * arr = new int[N];
    long long int max = -1;
    long long int min = 0;
    int tree;
    for(int i = 0; i < N; i++)
    {
        scanf("%d", &tree);
        arr[i] = tree;
        max = (max < tree) ? tree : max;
    }
    
    long long int mid;
    long long int total_timber;

    while(min <= max)
    {
        mid = (min + max) / 2;
        total_timber = 0;
        for(int i = 0; i < N; i++)
            if((arr[i] - mid) > 0) total_timber += (arr[i] - mid);
        if(total_timber < M) max = mid - 1;
        else min = mid + 1;
    }

    cout << max << endl;

    return 0;
}

ref

2805번: 나무 자르기

Top