[백준1114] 통나무 자르기

 

1114번: 통나무 자르기

풀이

처음 생각(오답) :

제일 긴 토막이 짧도록 만드려면

나무토막중 제일 긴 토막을 우선적으로 잘라야 한다.

우선순위 큐를 이용해 제일 긴 토막을 차례대로 뽑아낸다.

우선순위 큐는 [나무길이,나무시작점,나무끝지점] 으로 저장한다.

길이를 최소로 만들어야 하기 때문에 나무의 최대한 중간에 있는 위치를 잘라야 한다.

이분탐색을 통해 나무범위에 해당하는 후보중 중간위치((나무시작점+나무끝지점) // 2)와 가까운 인덱스를 찾는다.

이것을 C번 반복하면서 최대길이 나무와 잘랐던 지점 중 최솟값을 찾는다.

틀린이유 :

1. 우선순위 큐에 남아있는 나무 중 가장 큰게 최대길이 나무인 줄 알았는데 아니었다.

2. 후보를 찾으려 할 때 나무길이범위안에 후보가 아예 없는 경우가 있다.

3. 중간위치에 가까운 인덱스 찾는게 어렵다.

4. 중간 지점을 찾아서 자른다고 해도 그게 처음 자르는 위치가 제일 작은 경우를 반환하지 않는다.

• 10 3 2 / 1 2 5 가 주어졌을 때 지금 풀이대로라면 5를 선택하고 중간인 2를 선택한다. 그래서 답이 5,2가 출력된다.
• 하지만 5를 선택하고 1을 선택해도 정답 조건을 만족한다. 따라서 답은 더 작은 수인 5 1 이 된다.

그러므로 틀렸다.

다음 생각(정답) :

이분탐색을 통해 푼다.

가장 긴 조각의 길이(x)를 하나씩 던져본다.

함수를 통해 긴 조각의 길이가 x가 맞는지 확인한다.

• x를 고려해서 나무토막이 x보다 커지는 지점을 자른다. (후보군 간격이 x보다 작다면 자를 필요가 없고 x보다 크면 후보를 잘라야 최대길이가 x임을 만족한다.)
• 결과적으로 자르는 횟수(cnt)가 c 보다 크다면 x를 키운다. ( cnt가 크다는 것은 결과적으로 나무를 많이 잘랐다는것. x가 커야 cnt가 줄어든다. 또한 c보다 크면 정답이 아니다. c이거나 이하여야 한다.)
• 자르는 횟수가 c 이하라면 x를 줄인다. (여기서 정답이 나온다.)

여기서 더 생각해야 하는 부분 때문에 고생했다.

• 뒤에서 부터 잘라서 처음 자르는 위치가 제일 작도록 한다.
• 만약 cnt 가 C이하면 제일 왼쪽 후보를 추가적으로 자를 수 있다.
• 자르는 위치의 간격이 x보다 크다면 x가 최대길이인게 불가능하므로 종료처리하고 x를 키운다.

시간복잡도

결과적으로 x를 통해 cnt값을 찾는 연산을 이분탐색 횟수만큼 진행한다.

연산은 후보군들(K개)를 for문에 돌리며 cnt를 찾는다.

이분탐색은 log(L) 의 시간복잡도를 가진다.

결과적으로 시간복잡도는 K * log(L) 가 된다.

코드

L,K,C = map(int,input().split())
cuts = [0,L] + list(map(int,input().split()))
cuts.sort()

def solution(x):
    cnt = 0
    cut_start = L
    prev=[]
    first = 0
    # x라는 길이를 넘으면 자른다.
    for i in range(len(cuts)-1,-1,-1):
        diff = cuts[i] - cuts[i-1]
        total = cut_start - cuts[i]
        if diff > x:
            return 10001,0
        elif total > x:
            cut_start = cuts[i+1]
            prev.append(cuts[i+1])
            cnt+=1
        else:
            continue

    if cnt < C:
        first = cuts[1]
    else:
        first = prev[-1]

    return cnt, first

lo = 0
hi = L
answer = 0
first_cut = 0
while lo <= hi:
    mid = (lo+hi)//2

    cnt,first = solution(mid)

    if C < cnt:
        lo = mid+1
    else:
        answer=mid
        first_cut = first
        hi = mid-1


print(answer,first_cut)