[백준 2343번] 파이썬 - 기타 레슨

백준 2343 - 기타 레슨

시간 제한 2초, 메모리 제한 128MB

# 조건

• 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다.
• 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다.
• 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다.
  • 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.
• 강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다.
• 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다.
  • 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다.
  • 단, M개의 블루레이는 모두 같은 크기이어야 한다.
• 강토의 각 강의의 길이가 분 단위(자연수)로 주어진다.
• 이때, 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 강의의 수 N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)이 주어진다.
• 다음 줄에는 강토의 기타 강의의 길이가 강의 순서대로 분 단위로(자연수)로 주어진다.
• 각 강의의 길이는 10,000분을 넘지 않는다.

출력

• 첫째 줄에 가능한 블루레이 크기중 최소를 출력한다.

# 접근 방법

• 이분 탐색과 매개변수 탐색을 활용한다.
• 1개의 블루레이가 가질 수 있는 최소 크기는 주어진 동영상 중 최대 크기 이며, 가장 큰 경우는 => 모든 동영상 크기의 합이다.
• 즉, left = max(nums), right = sum(nums)로 잡아주며, left <= right 조건을 충족하는 경우까지 while문을 돌려준다.
• while문 로직은 아래와 같다.
  • mid = (left + right) // 2를 통하여 중간 값으로 잡아준다.
  • 부분 합 변수 1개, 사용한 블루레이 개수 변수 1개를 0과 1로 초기화 한후, for 문을 돌려준다.
  • 연속된 동영상의 크기가 mid를 넘지 않을 때까지 더해준 후, mid보다 커진다면 현재 동영상의 크기로 초기화, cnt+1을 하여 블루레이를 하나 추가해준다.
  • 반복문이 끝난 후 사용된 블루레이가 K보다 크다면 left를 mid+1로 변경하여 블루레이의 최대 크기를 늘려주고,
  • 블루레이를 k보다 작게 사용했다면 right를 mid-1로 해주며 최대 크기를 줄여준다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline

N, M = map(int, input().split())
nums = list(map(int, input().split()))
result = float('inf')
left = max(nums)
right = sum(nums)
while left <= right:
mid = (left + right) // 2
val = 0
cnt = 1
for i in range(N) :
    val += nums[i]
    if val > mid:
val = nums[i]
cnt += 1
if cnt <= M :
    result = min(result, mid)
    right = mid - 1
else:
left = mid + 1
print(result)