99클럽 코테 스터디 _ 4일차 TIL (이분탐색)

 

< 문제 >

[백준] 2343. 기타 레슨 / 실버1

---

< 풀이 >

코드 변수 정의

• videos : 강의의 길이가 담긴 리스트
• play_time : 한 블루레이에 들어간 영상의 길이
• cnt : 최대 영상 길이(mid)에 따라 생성되는 블루레이 총 개수
• ans : 가능한 블루레이 크기 중 최솟값

---

Binary Search
시간복잡도 : O(N * log(sum(videos)))

def binary_search(videos, M):
    left, right = max(videos), sum(videos) # 블루레이 개수: N개, 블루레이 개수: 1개
    ans = 0
    while left <= right:
        mid = (left + right) // 2 # 한 블루레이당 최대 영상 길이
        play_time, cnt = 0, 1 
        cnt = 1

        for video in videos: # 최대 영상 길이에 따라 생성되는 블루레이 개수 구하기.
            if play_time + video > mid:
                cnt += 1
                play_time = 0
            play_time += video

        if cnt <= M:
            ans = mid
            right = mid - 1 # 더 짧은 영상 길이로 (블루레이 개수 ⬆︎)
        else:
            left = mid + 1 # 더 긴 영상 길이로 (블루레이 개수 ⬇︎)

    return ans

def f():
    N, M = map(int, input().split())
    videos = list(map(int, input().split()))
    print(binary_search(videos, M))

f()

• 이분 탐색
  
  • point. 한 블루레이당 최대 영상 길이(mid)를 기준으로 탐색한다.
  • left는 블루레이의 개수가 N개인 경우 → 모두 같은 크기의 블루레이기 위해서 max(videos)로 지정
  • right는 블루레이의 개수가 1개인 경우 → 전체 강의가 하나의 블루레이에 들어가 있으므로 sum(videos)로 지정
  • (작동 방식)
    • mid를 기준으로 블루레이에 영상을 담았을 때 생성되는 블루레이 개수(cnt)
    • cnt <= M 인 경우
      • mid를 정답값으로 업데이트한다.
      • 최대 영상 길이를 더 짧은 범위에서 확인한다. (right = mid - 1)
      • 이유 : 가능한 블루레이의 크기 중 최소를 구하는 것이며 블루레이 개수가 M보다 적으므로 더 늘려도 된다.
    • cnt > M 인 경우
      • 최대 영상 길이를 더 긴 범위에서 확인한다. (left = mid + 1)
      • 이유 : 블루레이 개수가 M보다 많으므로 한 블루레이당 크기를 늘려서 더 많은 영상이 들어가게 해야 한다.

 

---

< 회고 >

이분 탐색을 어떤 식으로 적용해야 할지에 대해서 생각해 내는데 시간이 많이 소요됐다.

1. (생성되는 블루레이 개수) 1 ~ M까지를 범위로 설정
   
   • 개수에 따라 또 강의를 어떻게 나눠야 할지 모르겠다.
   • 완전 탐색으로 이어지면 시간초과가 발생할 것 같다.
2. (블루레이 개수별 최대 영상 길이) max(videos) ~ sum(videos)를 범위로 설정
   
   • for문으로 영상 길이 확인하며 생성되는 블루레이 개수를 체크할 생각을 하는 게 어려웠다.
   • while문 내에서 for문을 쓰는 것에 대한 두려움인가..

 

 

 

Binary Search를 다양하게 적용하는 법에 대해서 공부할 필요성을 느꼈다.