[Python/Java] 백준 2343 - 기타 레슨 [이진 탐색]

문제

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

 

해설

이진 탐색을 활용하여 해결하는 문제였다. 분할하는 구간들 때문에 아이디어가 곧바로 떠오르지 않아서 시간이 꽤 오래 걸렸다.

 

Python

from sys import stdin


def chk_validation(M: int, videos: list, max_size: int):
    running_time = 0
    blue_ray_cnt = 1

    for video in videos:
        if max_size < (running_time + video):
            running_time = video

            blue_ray_cnt += 1
            if M < blue_ray_cnt:
                return False
        else:
            running_time += video

    return True


def solution(N: int, M: int, lst: list):
    start = max(lst)
    end = sum(lst)

    result = end
    while start <= end:
        mid = (start + end) // 2

        if chk_validation(M, lst, mid):
            result = mid
            end = mid - 1
        else:
            start = mid + 1
    print(result)


n, m = map(int, stdin.readline().split(" "))
videos = list(map(int, stdin.readline().split(" ")))
solution(n, m, videos)

 

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input1 = br.readLine().split(" ");
        int n = Integer.parseInt(input1[0]);
        int m = Integer.parseInt(input1[1]);

        String[] input2 = br.readLine().split(" ");
        List<Integer> videos = new ArrayList<>();
        for(String v : input2){
            videos.add(Integer.parseInt(v));
        }

        int start = Collections.max(videos);
        int end = videos.stream().mapToInt(Integer::intValue).sum();
        
        int result = end;
        while(start <= end){
            int mid = (start + end) / 2;
            
            if(checkValidation(m, videos, mid)){
                result = mid;
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        System.out.print(result);
    }

    public static boolean checkValidation(int M, List<Integer> videos, int maxSize) {
        int runningTime = 0;
        int bluerayCnt = 1;
        
        for(int video : videos){
            if(maxSize < (runningTime + video)){
                runningTime = video;
                bluerayCnt++;
                if(M < bluerayCnt){
                    return false;
                }
            } else{
                runningTime += video;
            }
        }
        return true;
    }
}