백준 2343번: 기타 레슨 (Python/Java)

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

2343번: 기타 레슨

 

 

 

접근

---

이분 탐색 문제에서 가장 먼저 찾아야 할 것은 이분 탐색의 범위다. 최솟값과 최댓값을 알아야 둘로 나누어 탐색할 수 있기 때문이다. 이 문제에서 최솟값은 레슨 목록 중 가장 길이가 긴 레슨의 시간이다. 레슨은 나누어 저장할 수 없고 블루레이 하나에 무조건 저장이 되어야 한다. 어떤 레슨을 넣더라도 하나의 블루레이 디스크에 다 저장할 수 있으려면 블루레이 디스크가 레슨 중 가장 길이가 긴 레슨을 저장할 수 있어야 한다. 최댓값은 너무 당연하게도 모든 레슨을 하나의 디스크에 저장했을 경우의 값이다.

 

위와 같은 방법으로 구한 블루레이 디스크의 크기를 기준으로 레슨을 저장한다. 이때 레슨을 모두 저장하기 위해서 필요한 디스크 수가 처음 조건으로 주어졌던 디스크 수보다 많다면 디스크의 크기를 높인다. 적다면 디스크 크기를 줄인다. 이를 반복하면 해당 문제의 답을 구할 수 있다.

 

 

 

풀이

---

Python

lessonNum, bluerayNum = map(int, (input()).split())

lessonList = []
start, mid, last, result = 0, 0, 0, 1000000000
firstLine = (input()).split()
for i in range(lessonNum):
    lessonList.append(int(firstLine[i]))

    last += lessonList[i]
    start = max(lessonList[i], start)

while start <= last:

    mid = (start+last)//2

    subResult = 0
    checkNum = 0
    for i in range(lessonNum):

        if checkNum+lessonList[i] > mid:
            checkNum = 0
            subResult += 1
        checkNum += lessonList[i]

    if checkNum != 0:
        subResult += 1

    if subResult > bluerayNum:
        start = mid + 1
    else:
        last = mid - 1
        result = min(result, mid)

print(result)

 

Java

import java.util.Scanner;

public class Main {
   
    public static void main(String[] args) {
        
        Scanner scan = new Scanner(System.in);

        String[] firstLine = (scan.nextLine()).split(" ");
        int lessonNum = Integer.parseInt(firstLine[0]), bluerayNum = Integer.parseInt(firstLine[1]);

        int[] lessonList = new int[lessonNum];
        int start = 0, mid = 0, last = 0, result = 1000000000;
        
        String[] secondLine = (scan.nextLine()).split(" ");
        for(int i = 0 ; i < lessonNum ; i++){
            lessonList[i] = Integer.parseInt(secondLine[i]);

            last += lessonList[i];
            start = Math.max(lessonList[i], start);
        }

        while(start <= last){
            mid = (start+last)/2;

            int subResult = 0, checkNum = 0;
            for(int i = 0 ; i < lessonNum ; i++){
                if((checkNum + lessonList[i]) > mid){
                    checkNum = 0;
                    subResult += 1;
                }

                checkNum += lessonList[i];
            }

            if(checkNum != 0){
                subResult += 1;
            }

            if(subResult > bluerayNum){
                start = (mid + 1);
            }else{
                last = (mid - 1);
                result = Math.min(result, mid);
            }
        }

        System.out.println(result);

    }

}

 

 

 

후기

---

습관이라는 것이 참 무섭다. 문제 조건에서 분명히 강의 순서를 바꾸면 안된다고 주어졌는데 아무 생각 없이 sort를 했다. 굉장히 습관처럼, 그리고 기계적으로 문제를 풀고 있었다는 뜻이기도 하다. 문제를 풀 때, '이전에 그렇게 풀었으니'가 아니라 '이런 조건으로 인해 이렇게'라는 생각으로 풀어야겠다.