나무를 자르다니 나무해 (백준 2805:나무자르기)

2805번: 나무 자르기 (acmicpc.net)

2805번: 나무 자르기

나무의 수 : N

원하는 나무의 길이 : M

 

상근이가 환경에 관심이 많기 때문에 최소한의 나무만 자르고 싶다고 한다.

정말 기특하지 아니할 수 없다.

상근이를 위해서 열심히 풀어보자.

 

 

 - 대전략

항상 수능을 공부할 때 들었던 말이 있다.

 

"출제자의 의도를 파악하라."

 

다행히도 백준의 출제자의 의도는 알고리즘 분류에 나타나있다. 

이 문제의 알고리즘 분류는 이분 탐색이다. 이분 탐색으로 풀어보자. 

 

이분 탐색이 무엇인가. 흔히 말하는 업다운 게임이다. 절반부터 탐색하여 차이를 반씩 줄여나가는 탐색법이다. 

 

일단 나무를 높이 순으로 정렬하자. 알기쉽게 오름차순으로 정렬할 것이다.

 

그리고 여기서 분기가 나뉘는데, 최장 길이와 최단 길이를 할 것이냐, 아니면 리스트의 첫값과 마지막값을 구할 것이냐에서, 정석대로 위치로 가겠다. 나무의 최장 길이의 위치(tree[len(tree)-1]와 최단 길이 위치(tree[0])를 구해서 중간위치를 구하는 식으로 가자.

 

다만, 여기서 중요한 것은 값을 찾는 것이 아니라 나무의 길이를 구한다는 것이다. 업다운으로 진출하는 조건은 나무의 길이를 구해서 가야된다는 것이다. 

 

그렇다면, 나무를 높은 순으로 일렬로 쭉 세워서, 숫자(절단기의 높이 : H)를 지정하고 잘라본다. 

만약 길이 누적 값이 M 보다 높다면 다시 숫자를 낮춰서 하는 식으로 하면 어떨까. 

 

그리고 이 숫자를 찾는 것을 이진 탐색으로 하는 것이다.

다만, 문제가 있는 것이 최소한 M 미터를 확보해야 된다는 것이다. 즉, 딱 M 미터를 확보할 수 없을지도 모른다.

 

이 간극을 어떻게 해결할 것인가?

 

그렇다면, 귀결 조건은 어느 H 미터에서는 M을 확보하고, H-1에서는 M을 확보하지 못하는 것이다.

그 말인즉슨, H미터로 자르다가 누적 길이(length)가 M을 넘어갔을 때, 다음 나무가 H 미터 이하인 경우이다. 

 

 

 

그럼 게임을 시작해보자.

우선, 인풋을 받아오자.

N, M = map(int, input().split())
tree = list(map(int,sys.stdin.readline().split()))
tree.sort(reverse=True)

그리고 나무 길이를 판별하는 식을 만들자.

판별식은 H를 정하고, 높은 순부터 잘라가면서 M과 비교한다.

import sys

sys.stdin = open("input.txt","r")


N, M = map(int, input().split())
tree = list(map(int,sys.stdin.readline().split()))
tree.sort(reverse=True)

def find():
    global M
    left = 0
    right = len(tree)-1
    

    high = tree[0]
    low = tree[len(tree)-1]
    length = 0

    while True:
         # 첫 H
        # print("tree[mid]:", tree[mid])
        for i in range(len(tree)):
            H =( high + low ) // 2
            if H >= tree[i]:
                break
            length += (tree[i] - H)

            # if, elif : 나무 누적 길이가 딱 일경우
            if length >= M and i <= len(tree)-2 and tree[i+1] <= H:
                return H

            elif length >= M and i == len(tree)-1:
                return H

            # 너무 많이 자를 경우
            else:
                low = H + 1
        high = H - 1

print(find())

 

예제는 통과했으나, 런타임 에러가 나온다.

어딘가에 잘못된 식이 있다는 것이다.

 

또한,  2 3 // 2 2 를 넣었을 때, 0이 아니라 1이 나온다.

일단 이것부터 손보기로 하자.

 

low 가 가장 작은 나무의 길이로 되어있는데, 이것을 0으로 수정하겠다. (위의 반례에서 H가 가장 작은 나무보다도 낮은 수일 수 있으므로)

 

수정한 코드는 다음과 같다.

import sys



N, M = map(int, input().split())
tree = list(map(int,sys.stdin.readline().split()))
tree.sort(reverse=True)

def find():
    global M
    high = tree[0]
    low = 0
    

    while True:
        length = 0
         # 첫 H
        # print("tree[mid]:", tree[mid])
        for i in range(len(tree)):
            H =( high + low ) // 2
            # if H >= tree[i]:
            #     break
            length += (tree[i] - H)

            # if, elif : 나무 누적 길이가 딱 일경우
            if length >= M and i <= len(tree)-2 and tree[i+1] <= H:
                return H

            elif length >= M and i == len(tree)-1:
                return H

            # 너무 많이 자를 경우
        if length >= M:
            low = H + 1
            
        else:
            high = H - 1

print(find())

 

그리고 틀렸다고 나온다.

아마 시간 초과는 무한루프를 돌고 있었던 것 같다.

 

판별식에서 틀린 곳을 잘 찾아보자.

 

4 10

20 15 10 17 1 2 3 4 5 6

를 돌렸을 때, 다시 10이 나온다. 수정해주자.

 

while True:
        length = 0
         # 첫 H
        # print("tree[mid]:", tree[mid])
        for i in range(len(tree)):
            H =( high + low ) // 2
            # if H >= tree[i]:
            #     break
            length += (tree[i] - H)

            # if, elif : 나무 누적 길이가 딱 일경우
            if length >= M and i <= len(tree)-2 and tree[i+1] <= H:
                return H

            elif length >= M and i == len(tree)-1:
                return H

            elif length >= M:
                low = H + 1
                
        else:
            high = H - 1

elif 와 else 쪽을 수정하였다. 

그럼에도 불구하고 다시 틀렸습니다가 나온다.

반례가 필요하다.

 

5 2

9 9 9 9 9

에서 답이 9로 나온다. 원래 답은 8이어야 한다. 수정해주자.

 

최댓값을 찾기 위해서 판별식에서는 8로 잘라도 다음 나무가 H보다 크면 넘어가게 되어있다. (한번 더 위에서 진행함)

 

이 조건을 없애도 되나? 아니면 조건식을 아예 새로 만들어줘야하나?

지금 생각나는 것은 현재 자른 나무(i)가 마지막 나무보다 크다면, 넘겨주고 같다면 멈추는 것이다. 

 

그리고 간과했는데, 높이는 최대한 높아야 한다. 

 

다시 판별식을 짜주자.

 

나무가 무조건 딱 맞게 나왔다면 거기서 스탑이다. 

 

나무가 부족한데, 나무가 H 이하라면, high를 H보다 한칸 내려준다.

 

부족한 상태에서 i가 끝나도 high를 내려준다.

 

나무가 남는데, 다음 나무가 H보다 높다면 low를 H보다 한칸 올려준다.

 

그리고 항상 나무가 충분해야 끝나므로, while break 조건에 나무가 충분할 때를 넣어준다.

import sys



N, M = map(int, input().split())
tree = list(map(int,sys.stdin.readline().split()))
tree.sort(reverse=True)

def find():
    global M
    high = tree[0]
    low = 0
    

    while True:
        length = 0
         # 첫 H
        # print("tree[mid]:", tree[mid])
        H =( high + low ) // 2
        for i in range(len(tree)):
            
            # if H >= tree[i]:
            #     break
            length += (tree[i] - H)

            # 딱 길이가 맞을 때,
            if length == M and tree[i] <= H:
                return H

            elif length < M and tree[i] <= H:
                high = H - 1
                break

            elif length < M and i == len(tree) - 1:
                high = H - 1
                break

            elif length >= M and tree[i] >= H:
                low = H + 1
                break
        
        if high < low and length >= M:
            break
    return H
        
            


print(find())

파이썬으로 돌렸을 때는 70% 정도에서 패배했지만, 파이파이는 통과했으므로 일단 여기서 마치겠다.

나중에 파이썬으로도 돌아갈 수 있게 해보자.