99클럽 코테 스터디 Java 미들러 6일차 TIL - 나무 자르기 : 백준 2805번 - 이분탐색

 

1. 오늘의 문제 - 나무 자르기 - 백준 : 2805

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

 

이분탐색!

지금까지 갈고 닦은 이분탐색 실력을 뽐낼 시간이로군

 

2. 문제 풀이 전략

이건 그냥 이분탐색만 알고 알고 있으면 간단히 해결될 것 같다.

 

3. 난관 봉착... 예제 입력을 넣었을 때 출력이 제대로 안 나옴

근데 왜 첫 번째 예제 입력시 출력으로 15가 나와야 하는데 13이 나오는걸까? 

두 번째 예제도 마찬가지. 

36이 나와야 하는데 27이 나온다.

 

내가 작성한 로직은 아래와 같다.

int result = 0;
int left = 0;
int right = 1000000000;

while (left <= right) {
    int mid = (left + right) / 2;
    long cuttingTreesLength = 0;
    for (int currentTree : trees) {
        cuttingTreesLength += currentTree - mid;
    }
    if (cuttingTreesLength >= M) {
        result = mid;
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}

노트에다가 하나씩 그려가며 무엇이 잘못되었는지 확인해보았다.

 

4. 문제점 발견!

mid 값이 currentTree 보다 클 경우, 

음수값이 더해진다!

 

mid 가 13일 때,

20 - 13 = 7
15 - 13 = 2
10 - 13 = -3
17 - 13 = 4
총합: 10 (>= 7, 조건 만족)

 

mid가 14일 때,

20 - 14 = 6
15 - 14 = 1
10 - 14 = -4
17 - 14 = 3
총합: 6 (< 7, 조건 불만족)

 

따라서, 13이 답으로 출력되었던 것이다.

 

문제에서도, 높이 설정값이 나무보다 높으면 잘리지 않아야 한다고 그랬다.

따라서, 조건문을 넣어서 문제를 해결해야 한다.

 

5. 풀이

package io.conduktor.demos.dfsbfs.hanghaecote99.middler;

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

// 6. 나무 자르기 - 백준 : 2805 - 이분탐색
public class CuttingTree6 {

    static int N;
    static int M;
    static int[] trees;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        trees = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            trees[i] = Integer.parseInt(st.nextToken());
        }

        int result = 0;
        int left = 0;
        int right = 1_000_000_000;

        while (left <= right) {
            int mid = (left + right) / 2;
            long cuttingTreesLength = 0;
            for (int currentTree : trees) {
                if (currentTree > mid) {
                cuttingTreesLength += currentTree - mid;
                }
            }
            if (cuttingTreesLength >= M) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        bw.write(String.valueOf(result));

        bw.flush();
        bw.close();
        br.close();
    }
}

 

6. 소감

이분탐색 문제가 계속 푸니까 점점 익숙해진다.

 

이기고 있는 팀의 선수들은 얼굴에 미소가 번진다.

지고 있는 팀의 선수들은? 

 

승리는 열정을 불러 일으키고 패배는 열정의 불을 꺼뜨린다.

positive feedback loop의 시동을 걸린 듯 하다!