[Python] 2343번 기타 레슨

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

2343번: 기타 레슨

---

 

22/10/05

 

 

이분 탐색 문제로, 왜 이분 탐색으로 접근할 생각을 했냐고 묻는다면...

 

강의의 수가 최대 10만개이고, 강의의 길이는 최대 10000분이고, 블루레이 디스크의 최소 개수는 1개이기 때문에 가능한 블루레이의 크기는 최대 10만*10000 = 10억이다.

 

때문에 1분부터 10억분까지 일일이 선형으로 탐색하려면 시간이 너무 오래 걸릴 것 같아 이분 탐색으로 하기로 했다.

---

 

문제 접근 방식:

 

 

블루레이의 디스크에 강의를 순서대로 넣다가 더 이상 넣을 수 없을 때 다른 디스크에 넣는 과정을 이분 탐색할 때 구현하였다.

 

디스크의 크기가 mid라고 하면, mid에 강의들의 길이를 순서대로 빼준다. 그러다가 음수가 되면 새로운 디스크를 꺼내 그 디스크에 담으므로, 디스크의 개수를 +1해주고 다시 mid에 순서대로 빼준다.

 

이 과정을 강의들이 모두 담아질 때까지 계속 반복한다.

 

만약 블루레이 디스크가 M장 이하로 나온다면 디스크의 크기가 너무 커서 디스크를 적게 써도 강의가 다 담아진다는 뜻이므로, 우리는 강의가 다 담아질 수 있는 디스크의 크기의 최솟값을 찾아야 하므로 더 작은 쪽으로 이분 탐색을 진행한다.

 

만약 디스크가 M장보다 많이 나온다면, 혹은 디스크의 크기가 너무 작아서 강의 하나도 담지 못한다면, 강의가 다 담아지지 않는다는 뜻이므로, 더 큰 쪽으로 이분 탐색을 진행한다.

 

이분 탐색을 계속 진행하다가 low > high가 되었을 때에 종료하는 식으로 구현했다.

 

while문이 아닌, 재귀로 구현했다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 2343번 기타 레슨
# 그리디, 이분탐색
'''
접근 방법:
블루레이 크기를 이분탐색을 통해 찾는다.
이때 블루레이의 크기를 mid라고 하면 순서대로 넣기 때문에 mid에 guitar_lesson을
반복하여 순서대로 빼준다.
그런식으로 여러번 반복하여 블루레이가 M장 나온다면
그 중에서 우리는 최소 값을 찾아야 하므로 더 작은 쪽으로 이분탐색
만약 M장이 안나온다면 더 큰쪽으로 이분탐색
low >= high가 되면 종료한다.
'''
import sys
input = sys.stdin.readline

N, M = map(int, input().rstrip().split())
guitar_lesson = list(map(int, input().rstrip().split()))
def binary_search(low, high):
    mid = (low + high)//2
    if low >= high:
        return mid
    else:
        is_ok = True
        k = 0
        disks = 0
        for lesson in guitar_lesson:
            if lesson > mid:
                is_ok = False
                break
            k += lesson
            if k > mid:
                disks += 1
                k = lesson
        disks += 1
        if k > mid:
            disks += 1
            k = lesson
        if disks > M or not(is_ok):
            return binary_search(mid+1, high)
        else:
            return binary_search(low, mid)

ans = binary_search(1, int(1e9))
print(ans)