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

🥚문제

---

🥚입력/출력

---

🍳코드

import sys

n, m = map(int, sys.stdin.readline().rstrip().split())
forest = list(map(int, sys.stdin.readline().rstrip().split()))

# 절단기 설정 높이 h를 기준으로 이분 탐색 실행
start = 0
end = max(forest)
answer = 0
while start <= end:
    h = (start + end) // 2
    cutting = 0
    # 현재 h로 자를 수 있는 길이 구하기
    for tree in forest:
        if tree > h:
            cutting += (tree - h)
    if cutting >= m:
        # 일단 answer에 저장
        answer = h
        # h 늘려보기 (잘리는 길이 적게)
        start = h + 1
    elif cutting < m:
        # h 줄여보기 (잘리는 길이 많게)
        end = h - 1
print(answer)

📌나름의 포인트는 자른 길이가 m 이상일 때, 일단 answer에 저장하고 또 탐색을 하는 것이다. 적어도 m미터의 나무를 가져가기 위해 설정할 수 있는 높이의 최댓값을 찾는 것이므로, 더 큰 h에서도 m미터의 나무를 가져갈 수 있는 경우를 계속 찾아봐야 한다.

---

🧂아이디어

• 보는 바와 같이 엄청난 제출 끝에 겨우 '맞았습니다!!'를 받아낼 수 있었다.
• 처음에는 이분 탐색은 list 안에서 해야 한다는 고정관념이 있어서 나무 길이들을 리스트로 받은 뒤 그것을 정렬하고 안에서 설정한 높이 h 이상인 것이 처음 나타나는 인덱스를 찾아가는 형태로 진행했다. 그런데 5%? 10% 중에서 시간 초과가 뜬 것을 보면 잘못 생각했었던 것 같기도 하다.
• 결국 다른 사람들이 한 블로그를 찾아봤는데, 높이h를 이분탐색을 해가는 풀이 방법이 많았다.
• 이렇게 풀어내는 게 훨씬 쉬웠다. 다만, Python3로 제출했을 때는 50%정도에서 시간 초과가 떠서 놀랐다 (😨엥? 이것도 아니라고? 하는 느낌)
• PyPy3로 바꿔서 제출하니 겨우 '맞았습니다'가 떴다. PyPy3가 더 빠르다는 것은 익히 들어 알고 있었지만 이렇게 피부에 와 닿을 정도로 체험한 것은 오늘이 처음이다.
• 배울 점이 많은 문제였다.

🔽참고로 처음 생각했던 풀이 방법은 이렇다.

import sys

# 이진 탐색
# target 이상인 요소가 처음 등장하는 인덱스를 찾는다
def my_binary_search(array, start, end, target):
    while start <= end:
        mid = (start+end)//2
        if array[mid] >= target:
            # mid 보다 앞의 인덱스가 존재할 때
            if mid-1 >= 0:
                # 만약 앞의 요소도 target보다 크면, 앞의 요소의 인덱스 리턴
                if array[mid-1] > target:
                    return mid -1
                # 아니면 그냥 mid 리턴
                else:
                    return mid
        elif array[mid] < target:
            start = mid + 1

    # target 이상인 요소가 존재하지 않는다
    return -1

n, m = map(int, sys.stdin.readline().rstrip().split())
forest = list(map(int, sys.stdin.readline().rstrip().split()))
forest.sort() # 이진 탐색 수행하기 위해 정렬

# 절단기 설정 높이 h 이상인 나무가 처음 등장하는 인덱스를 찾는다
# h 도 이진탐색으로 해볼까?
found = False
h = forest[(n-1)//2] # h도 중간값에서 시작
while 0 <= h < forest[-1]:
    idx = my_binary_search(forest, 0, n-1, h)
    # 잘려나가는 나무들
    cutting_trees = forest[idx:]
    # 가져갈 수 있는 길이
    summation = sum(cutting_trees) - len(cutting_trees)*h
    if summation > m:
        print(h)
        # h의 길이 늘려본다
        h += 1
    elif summation < m:
        print(h)
        # h의 길이 줄여본다
        h -= 1
    else:
        print(h)
        break