[99클럽 코테 스터디 TIL 4일차 / 백준 2343] 기타 레슨 (Python)

이번주 문제들은 다 이분 탐색에 대한 문제인 것 같다.

 

처음에 문제를 풀고 단순히 모든 강의 길이의 합을 m으로 나누어 평균을 구하고, 모든 강의를 넣는 다면 평균 크기인 블루레이 몇개 필요한지 구했다. 만약 블루레이 개수가 m보다 크면 평균 +1 을 해주고 작으면 평균 -1 을 하여 m과 같을때까지 블루레이 개수를 구했다.

 

이렇게 코드를 작성하여 제출한 결과 당연히 실패가 떴다.

 

역시 시간초과를 해결할때는 이분탐색이 기본인 것 같다.

 

내 코드

n, m = map(int, input().split())

lessons = list(map(int, input().split()))

left = max(lessons)
right = sum(lessons)

while (left <= right):
    mid = (left + right) // 2

    cnt = 1
    b = 0
    for l in lessons:
        if b + l <= mid:
            b += l
        else: 
            b = l
            cnt += 1

    if cnt > m: left = mid + 1
    else: right = mid - 1

print(right + 1)

 

1. left에 가장 작은 블루레이 크기인 가장 긴 강의의 길이 값을 넣어준다.

2. right에 가장 큰 블루레이 크기인 모든 강의 길이의 합을 넣어준다.

3. mid 값을 구해준 뒤, 블루레이 크기를 mid로 설정하고 몇개의 블루레이가 필요한지 구한다.

4. 필요한 블루레이 개수가 m보다 크면 left = mid + 1을 해주고 다시 구한다.

5. 필요한 블루레이 개수가 m보다 작으면 right = mid - 1을 해주고 다시 구한다.

 

이렇게 이분탐색을 통해 코드 구현을 하였다 !!

 

왠만한 탐색에서 시간초과는 이분탐색으로 해결이 되는 것 같다 ! 꺄울

이분탐색을 알게되니 문제 푸는 시간이 많이 줄었다 ~!

 

오픽을 담주 수욜로 미루려고 했는데 평일 오픽 시험 시간은 알바 시간이랑 다 겹쳐서 담주 토욜로 미뤘다 ..

너무 루즈해지는 건 싫은ㄷㅔ ㅜㅜ

제발 IH 받게 해주세열 ~~

 

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