[백준] 17179 - 케이크 자르기

문제 링크

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

문제 요약

• 롤 케이크의 길이와 자를 수 있는 위치가 주어집니다.
• 각 자르는 횟수(Qi)에 대해, 케이크를 해당 횟수만큼 잘랐을 때 가장 작은 조각의 길이가 최대가 되도록 자르는 방법을 찾아야 합니다.
• 각 자르는 횟수에 대해 가장 작은 조각의 길이의 최댓값을 구하는 것이 목표입니다.

푼 방법

 

• 이분 탐색의 적용 범위 설정:
  • 가능한 답의 범위는 1부터 케이크 전체 길이(L)까지입니다. 즉, 가장 작은 조각의 길이의 최댓값을 찾는 것이므로 최소값은 1, 최댓값은 케이크의 전체 길이(L)로 설정합니다.
• 이분 탐색 시작:
  • 중간값 X를 선택합니다. 이 X는 "가장 작은 조각의 길이의 후보"입니다.
  • 각 자르는 횟수(Qi)에 대해, 케이크를 X 이상의 길이를 유지하면서 자를 수 있는지 확인합니다.
• 자르는 방법:
  • 자를 수 있는 위치 Si와 롤 케이크 끝(L)을 기준으로, 각 조각의 길이가 X 이상이 되도록 자를 수 있는지 확인합니다.
  • 만약 X 이상으로 자를 수 있다면, 해당 조각의 길이를 만족할 수 있는 경우입니다.
  • X 이상으로 자를 수 없다면, X를 줄여야 합니다.
• 조건 검증:
  • 만약 중간값 X로 조각을 자르는 것이 가능하면, 더 큰 X 값도 시도해 볼 수 있습니다(즉, 작은 조각의 길이를 최대화하는 방향으로 이분 탐색 범위를 늘림).
  • 반대로, 불가능하다면 X를 줄여야 합니다(즉, 가능한 값으로 이분 탐색 범위를 좁힘).
• 최종 답 도출:
  • 이분 탐색을 통해 가장 작은 조각의 길이가 최대가 되는 값을 찾습니다.

 

정답 코드

import sys
n, m, l = map(int, sys.stdin.readline().split())

cake = []
for i in range(m):
    cake.append(int(sys.stdin.readline().rstrip()))
cake.sort()

dist = [0] + cake + [l]

def chk(mid, slice):
    temp = 0
    prev = 0
    for i in range(len(dist)):
        if dist[i] - prev >= mid:
            temp+=1
            prev = dist[i]
    
    return temp <= slice

for i in range(n):
    q = int(sys.stdin.readline().rstrip())
    s , e = 1, l
    while s<=e:
        mid = (s+e)//2
        
        if chk(mid, q):
            e = mid - 1
        else:
            s = mid + 1
    
    print(e)