1 minute read

문제

접근 방법

문제를 읽으면서 가능한 모든 크기들을 다 따져봐야한다는 생각이 들었다. 하지만 모든 경우의 수를 확인하기 위해서는 강의 영상 중 최대 길이값부터 모든 강의의 길이의 합의 값까지 다 확인해야 한다. 그렇다면 100,000 ~ 1000000000(100,000 x 10,000)까지 다 확인해야 하기 때문에 시간을 초과하게 된다.

생각해낸 방법이 이진 탐색을 통해 탐색 시간을 logN으로 하는 것이었다. 각 블루레이의 최적의 크기를 이진 탐색으로 찾으면 시간 안에 다 확인할 수 있게 된다. 설정한 mid 값으로 담는다고 할 때, 얼만큼의 블루레이가 필요할지 계산하는 알고리즘은 O(N)이므로 전체 O(NlogN)으로 문제를 해결할 수 있게 된다.

정답 코드


import sys
input = sys.stdin.readline


"""
블루레이 크기의 경우의 수는 엄청 많음.
이 중 최소를 구하려면 이분 탐색을 통해 제일 작은 경우의 수를 구해야 할 거 같음

범위를 한 강의의 최대 길이~모든 강의의 합으로 해야할 듯

mid 크기로 다 담을 수 있다면 그 값 저장하고 더 작은 사이즈 확인

mid 크기로 못 담는다면 더 큰 사이즈 확인
"""
min_size = 0


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

start = max(lectures)
end = sum(lectures)

while start<=end:
  mid = (start + end)//2

  """
  mid 크기의 블루레이로 전체 강의를 담는 알고리즘
  """
  total = 0
  #mid 크기로 담는데 소요되는 블루레이 수
  cnt = 1
  for lect in lectures:
    # 현재 강의를 담음으로써 크기를 초과한다면
    if total + lect > mid:
      cnt+=1
      total = lect
    # 현재 강의를 담을 수 있다면
    else:
      total += lect

  #mid 크기로 충분히 담는다면
  if cnt <= m:
    min_size = mid
    end = mid-1
    
  #mid 크기가 너무 크다면
  else:
    start = mid+1

print(min_size)

You May Also Enjoy