백준 1114 통나무 자르기

문제

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

풀이

k개의 위치중에 c개를 선택하는 경우의 수는 너무 많으니 해당 접근법은 포기하고, 통나무의 가장 긴 조각의 크기를 x라고 했을 때 제한된 커트 안에 짜를 수 있을까를 결정해야 하는 문제이다.

처음 위치가 가장 작은 위치를 구해야 하기 때문에, 뒤에서 부터 최대한 잘라놔야 하기 때문에 뒤에서부터 자른다.
결정값이 주어졌을때,
1) 자르는 위치를 기준으로 앞의 위치와 비교해 해당 결정값보다 크면 결정값 이하로 절때 자를 수 없기 때문에 10001을 반환해 불가능 함을 반환해준다.

2) 앞의 위치와 값 차이를 냈는데, 결정값보다 작다면 해당 위치에서는 자르지 않아도 되기 때문에 결정값보다 커질때까지 탐색한 뒤, 결정값보다 커지면 찾은 위치의 뒷부분을 짤라주어야 한다.

이렇게 찾은 후, 자른 횟수가 c보다 많다면 결정값이 현재 값보다는 커야한다는 의미이고, 자른 횟수가 c보다 작다면 현재 결정값보다 더 작은 값이 있나를 찾으면 된다.

l,k,c = list(map(int,input().split()))
arr = [0,l] + list(map(int,input().split()))
arr.sort()
def check(x): ## 가장 긴 조각이 x 보다 작아질 수 있을까? => 모든 자른거가 길이가 x보다 작아야함
    cnt = 0
    pos = l
    cutted = []
    for i in range(len(arr) - 1, -1, -1):
        dist = arr[i] - arr[i - 1]
        total = pos - arr[i]
        if dist > x:
            return 10001,-1
        elif total > x:
            pos = arr[i + 1]
            cutted.append(arr[i + 1])
            cnt += 1
    if cnt < c: return cnt, arr[1]
    else: return cnt, cutted[-1]

def go():
    start = 0
    end = l
    a,b = 0,0
    while start + 1 < end:
        mid = (start + end) // 2
        cnt, pos = check(mid)
        if cnt > c:
            start = mid
        else:
            a = cnt; b = pos
            end = mid
    print(end,b)
go()

boj 카테고리 내 다른 글 보러가기