[Python/파이썬] 백준 17179번 케이크 자르기

 

17179번: 케이크 자르기

 

문제

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

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

입력

첫 번째 줄에 자르는 횟수가 담긴 목록의 길이 N과 자를 수 있는 지점의 개수 M, 그리고 롤 케이크의 길이인 정수 L이 주어진다. (1 ≤ N ≤ M ≤ 1,000, 1 < L ≤ 4,000,000)

다음 M줄에 걸쳐 자를 수 있는 지점을 나타내는 정수 $S_i$가 주어진다. (1 ≤ $S_i$ < L)

다음 N줄에 걸쳐 자르는 횟수를 나타내는 정수 $Q_i$가 주어진다. (1 ≤ $Q_i$ ≤ M)

$S_i$는 오름차순으로 주어지고 중복되는 수는 없으며, $Q_i$도 마찬가지이다.

출력

N개 줄에 걸쳐 각 목록에 있는 횟수대로 롤 케이크를 잘랐을 때 가장 작은 조각의 길이의 최댓값을 출력한다.

코드

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


def chk(min_l):
    s, cnt = 0, 0
    for loc in cut_loc:
        if loc - s >= min_l:
            cnt += 1
            s = loc
    return cnt  # 잘라진 조각 개수


for num in cut_num:
    start, end = 1, l
    ans = 0
    while start <= end:
        mid = (start+end) // 2
        if chk(mid) > num:  # 원하는 횟수 이상으로 자르기 가능
            start = mid + 1
            ans = max(ans, mid)
        else:
            end = mid - 1
    print(ans)

이분탐색을 이용하여 조건을 만족하는 최대값을 찾는 알고리즘인 매개 변수 탐색을 이용하여 푸는 문제였다.

시작과 끝값은 각각 1, 케이크 길이(l)로 두고 이분탐색을 진행한다. 이때 mid 값은 가장 작은 조각의 크기를 뜻한다.

chk() 함수는 매개변수로 주어진 길이 이상으로 자를 수 있는 케이크 조각들의 개수를 리턴한다.

자를 수 있는 조각의 수는 자른 횟수보다 1 크기 때문에 chk(mid) > num인지 확인하여 가능하다면 ans에 ans와 mid 중 큰 값을 저장하고 더 큰 조각이 가능한지 알아본다.