[Algorithm] 99클럽 코테 스터디 4일차 TIL | 백준_기타 레슨(2343번)

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

---

오늘도 이분탐색..^^

문제의 접근 방법에 대해서만 살짝 gpt한테 엿듣고

 

low를 가장 긴 녹화 길이로,

high를  모든 녹화 길이의 합으로 설정한 후

 

블루레이 크기를 mid로 잡는 것을 시작으로 차근차근 풀어나간 문제다.

(답을 보지않고 맞혔다는 것에 큰 희열 🥲 나..이제 이분탐색 마스터?)

 

이 문제의 핵심은 mid 값으로 잘랐을 때 M개로 나눌 수 있는가? 이다.

 

만약 나눈 값이 M보다 크면

mid 값을 더 크게 잡아야 하므로 low = mid + 1을 해주고

 

나눈 값이 M보다 작거나 같다면 

mid값을 더 작게 잡아야 하므로 high = mid - 1을 해준다.

이때 정답이 나올 수 있으므로 result값에 mid를 넣어주었다. (최솟값을 찾아야하므로,,)

if(cnt <=  M){
    high = mid - 1;
    result = mid;
}else{
    low = mid + 1;
}

 

전체 풀이

import java.util.*;
import java.io.*;
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[] arr = new int[N];

        int max = 0;
        int sum = 0;

        st = new StringTokenizer(br.readLine(), " ");

        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
            max = Math.max(max, arr[i]);
            sum += arr[i];
        }

        int low = max;
        int high = sum;
        int result = 0;

        while(low <= high){
            int mid = (low + high) / 2;

            int key = 0;
            int cnt = 1;

            for(int i = 0; i < N - 1; i++){
                key += arr[i];
                if(mid < key + arr[i+1]){
                    cnt++;
                    key = 0;
                }
            }
            if(cnt <=  M){
                high = mid - 1;
                result = mid;
            }else{
                low = mid + 1;
            }
        }
        System.out.println(result);
    }
}

 

오늘은 공책에 필기해가면서 풀었더니 더 정리가 잘 되는 느낌이다.

역시 암산은 나랑 안 맞아(?)