[TIL] 99클럽 코테 스터디 6일차 TIL + 백준 2805 나무 자르기

 

문제 풀이

 

 

문제 탐색하기

이분탐색을 활용하여 문제 설계하기

이분탐색에 대한 개념은 아래 게시글에 정리해두었습니다!

https://coding-babo.tistory.com/148

[TIL] 99클럽 코테 스터디 1일차 TIL + 이분 탐색

 

바로 이분탐색을 이용하여 문제를 파악해보겠습니다.

상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어집니다. 적어도 M을 맞추기 위한 절단기의 높이를 구하는 것이 이 문제의 답입니다.

여기서 이분탐색을 실행할 범위를 구할 수 있습니다.

 

이분탐색 범위

• left : 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이므로 0으로 설정합니다.
• right : M이 1보다 같거나 크기 때문에 무조건 나무를 절단해서 가져간다는 뜻입니다. 따라서 절단기에 설정할 수 있는 최대 높이는 주어진 나무의 높이 중 가장 큰 높이를 설정할 수 있습니다.

이분탐색 구현 아이디어

1. left 와 right 중간 mid 값은 절단기 높이 값입니다.
2. 나무들을 절단기로 잘랐을 때 잘려진 나무의 길이를 저장할 변수 hap을 선언합니다.
3. 나무 높이를 저장한 배열을 for문으로 탐색하며 나무의 높이에서 mid를 뺀값을 구합니다.
4. 해당 값이 0보다 작으면 나무를 자르지 않았다는 뜻으로 0을 hap 에 더하고 0보다 크면 그 값이 잘려진 나무의 길이므로 hap 에 더해줍니다. 
5. hap 의 값이 상근이가 가져가려고 하는 나무의 길이 M보다 클 경우 left = mid + 1 해주고 작을 경우에는 right = mid - 1해줍니다.
6. left값이 right보다 커질때까지 탐색을 반복해줍니다. 

 

고려해야할 점

적어도 M미터의 나무를 집에 가져가야한다는 조건이 있습니다. 

만약에 예제가 아래와 같이 주어진다면 나무의 높이가 같기때문에 1에 딱 떨어지게 나무를 가져갈 수 없습니다.

따라서 절단기의 높이를 19로 설정하여 2미터의 나무를 가져가야합니다. 

이 조건을 고려하여 절단기 높이의 최대값은 이분탐색이 종료되었을 때 right의 값임을 알 수 있습니다.

2 1
20 20

 

 

문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int left = 0;
        int right = 0;
        int mid = 0;

        int[] trees = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            trees[i] = Integer.parseInt(st.nextToken());
            right = Math.max(right, trees[i]);
        }

        while(left <= right){
            mid = (left+right)/2;
            long hap = 0;
            for(int i=0; i<trees.length; i++){
                hap += trees[i]-mid < 0 ? 0 : trees[i]-mid;
            }

            if(hap >= M){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }

        System.out.println(right);
    }
}

 

 

 

오늘의 회고

99클럽에서 진행하는 코테 스터디를 한지 6일차 입니다! 매번 이분탐색(이진탐색) 문제를 풀때 오답의 연속으로 인해서 매번 도움을 받아서 문제를 마무리했었는데 처음으로 지금까지 풀었던 이분탐색을 토대로 스스로 문제를 마무리 할 수 있었습니다ㅎㅎ 흑.. 왜 미들러 단계 했냐며..