문제

생일을 맞이한 주성이가 생일 파티를 준비하려고 한다. 주성이는 일반 케이크 대신 평소 좋아하던 롤 케이크를 준비했다. 롤 케이크에는 장식이 존재해서 특정 위치에서만 자를 수 있다. 주성이는 롤 케이크 조각을 파티에 올 친구의 수 만큼 준비하고 싶어서, 가장 작은 조각의 크기를 미리 알아보기로 했다. 하지만 짓궂은 주성이의 친구들은 생일파티에 몇 명이 참석하는지 직접적으로 알려주지를 않는다. 그래서 몇 개의 수를 목록에 적어, 각 수만큼 조각을 만들었을 때 가장 작은 조각의 길이의 최댓값을 구하려고 한다.

예를 들어 70cm의 롤 케이크에 자를 수 있는 지점이 5군데(10cm, 20cm, 35cm, 55cm, 60cm)가 있다고 하자. 만약 목록에 적힌 수 중 하나가 3이라면 이때 가장 작은 조각의 길이는 최대 15cm이다. 예를 들어 20cm, 35cm, 55cm 지점을 자를 때 최대가 된다.

import sys

input = lambda: sys.stdin.readline().strip()

n, m, l = map(int, input().split())
arr = [int(input()) for _ in range(m)] + [l]


def counting(mini, q):
  left = 0
  count = 0
  for right in arr:
    if right - left >= mini:
      count += 1
      left = right
  if count > q:
    return True
  return False


for _ in range(n):
  q = int(input())
  start = 0
  end = l
  result = 0
  while start <= end:
    mid = (start + end) // 2
    if counting(mid, q):
      result = max(result, mid)
      start = mid + 1
    else:
      end = mid - 1

  print(result)

풀이

• 잘랐을 때 가장 작은 조각 : mid
• 케이크를 잘랐을 경우 가장 작은 조각이 mid 이상인 경우가 Q이상이어야 한다.

백준 17179 케이크 자르기