[백준/Python] 2343번: 기타 레슨

📁 문제

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

---

💭 풀이

① 블루레이에 총 N개의 강의가 들어감
② 각 강의를 블루레이 내에 순서대로 담아야 함 (순서 바뀌면 X)
③ M개의 블루레이는 모두 같은 크기

🧡 가능한 블루레이 크기 중 최소 구하기

임의의 블루레이 크기를 정하여 담아 본 다음

• 블루레이 개수가 M개보다
  • 많아지면 - 블루레이 크기 늘림
  • 적어지면 - 블루레이 크기 줄임

👆 이 부분을 이진 탐색

참고: https://yoongrammer.tistory.com/75

• high = 모든 강의를 더한 값
• low = 강의 중 길이가 가장 긴 강의

예제 입력값으로 보면 high = 45 , low = 9

🍰 알고리즘

1. mid = (low + high) // 2
   임의로 정한 블루레이 크기

2. 첫 번째 강의부터 하나씩 더함
   mid보다 값이 커지면 👉 필요한 블루레이 개수 + 1

3. 블루레이 개수 < M 👉 블루레이 크기 줄임
   high = mid - 1

4. 블루레이 개수 > M 👉 블루레이 크기 늘림
   low = mid + 1

---

🤍 코드

n, m = map(int, input().split())  # n = 강의의 수, m = 블루레이의 수
lesson = list(map(int, input().split()))

high = sum(lesson)  # 모든 강의를 더한 값
low = max(lesson)   # 강의 중 길이가 가장 긴 강의

while low <= high:
  sum = 0
  blu_ray = 0
  mid = (low + high) // 2       # 임의로 정한 블루레이 크기

  for i in range(n):
    if sum + lesson[i] > mid:   # mid보다 커지면
      sum = 0
      blu_ray += 1              # 블루레이 개수 1 증가
    sum += lesson[i]            # 첫 번째 강의부터 하나씩 더함

  if sum:   # mid보다 작아서 블루레이 개수를 증가시키지 못 한 경우
    blu_ray += 1

  if blu_ray <= m:
    high = mid - 1    # 블루레이의 크기 감소
  else:               # blu_ray > m
    low = mid + 1     # 블루레이의 크기 증가
    
print(low)