[백준]2805 나무자르기(Python)

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

2805번: 나무 자르기

 

문제 접근

 

우선 배열을 거꾸로 정렬한 후에 MAX부터 MIN까지 순차적으로 탐색하려고 했지만 실패했다. 

어짜피 비효율적이므로 뤼튼의 추천 코드는 이진탐색(이분탐색)

 

코드

import sys

input = sys.stdin.readline
# 입력 받는 부분은 그대로 유지합니다.
N, M = map(int, input().split())
trees = list(map(int, input().split()))

# 정렬은 필요하지 않으므로 제거
# trees.sort(reverse=True)
# 입력 5 20
# 4 42 40 26 46
# 출력 36

# 탐색할 최대 높이와 최소 높이 설정
MAX = max(trees)
MIN = 0

# 이진 탐색을 사용하여 원하는 합 M을 만족하는 높이 i 찾기 => 이 문제는 정렬 필요 X 주의
result = 0
while MIN <= MAX:
    mid = (MIN + MAX) // 2
    total = 0  # 계속 누적해나갈 변수 선언

    # trees 리스트의 각 원소에 대해 mid를 뺀 값을 더합니다.
    for tree in trees:
        if tree > mid:
            total += tree - mid

    # 원하는 합 M과 비교
    if total < M:   # 덜 잘라낸 듯 => 상한을 낮추기 위해 MAX 갱신
        MAX = mid - 1
    else:
        result = mid  # 이게 왜 필요한가 자꾸 생각.. 손으로 써보면 이해 가능 안쓰고 풀어보자
        MIN = mid + 1


print(result)

 

++틀린코드

    # 원하는 합 M과 비교
    if total < M:   # 덜 잘라낸 듯 => 상한을 낮추기 위해 MAX 갱신
        MAX = mid - 1
    else:
        # result = mid  # 이게 왜 필요한가 자꾸 생각.. 손으로 써보면 이해 가능 안쓰고 풀어보자
        MIN = mid + 1
        if total == M:
            print(mid)
            break

틀린 이유는 예시로 입력 값이 N:4 M:6 trees=[20,15,10,17]인 경우에는 아무리 탐색해도 합 6을 만족시키는 값이 없으므로 최대한 근접한 15로 잘라서 7을 가져가야 하므로 7을 출력해야 하지만 틀린 코드를 적용할 경우 total == M을 만족하는 값이 없으므로 아무것도 출력하지 않는다는 문제점이 있다.

 

++시간초과코드(순차탐색)

import sys

input = sys.stdin.readline
N, M = map(int, input().split())
trees = list(map(int, input().split()))

MIN = 0
MAX = max(trees)

result = 0

for cut_height in range(MAX, MIN - 1, -1): # 최대 높이부터 시작해서 0까지 
    total = 0
    for tree in trees:
        if tree > cut_height:
            total += tree - cut_height
    if total >= M: # 원하는 합 M에 도달하거나 초과한 경우
        result = cut_height # 결과를 갱신하고 계속 진행
        break

print(result)

 

회고

 

만약 시험 상황이었다면 나는 가장 익숙한 순차탐색으로 접근해서 결국 실패했을 것 같다.

그렇다면 만약 이 문제를 내가 순차탐색으로 풀었다면 어떤 코드를 작성했을 지 완성해 봐야 할 것 같다. 그리고 이분탐색의 경우 시간복잡도가 O(logN)이고 순차탐색의 경우 최악의 경우 시간복잡도가 O(N)이 되어버린다.