문제 출처 : https://www.acmicpc.net/problem/2805

---

문제 파악

• 나무의 개수 N
• 집에 가져가야 하는 최소 나무 길이 M (→ 여기선 변수 이름 target)
• 각 나무의 높이가 주어진다.

우린 절단기 높이 H 를 정해서

각 나무에서 max(나무높이 - H, 0) 만큼 잘라냈을 때,
그 잘라낸 나무 길이의 합이 target 이상이 되는 H 중, 가장 큰 H 를 찾아야 한다.

즉,

• 너무 낮게 자르면 → 가져가는 나무 길이는 많아지지만, 아깝다.
• 너무 높게 자르면 → 가져가는 나무 길이가 부족해진다.

그래서 “딱 필요 길이 이상은 되면서 최대한 높게 자르는 H”를 찾는 문제.

핵심 아이디어

1. 단조성(monotonicity) 확인

절단기 높이 H 를 기준으로 가져가는 나무 길이의 합을 생각해보자.

• H 를 낮게 잡을수록 → 더 많이 잘려 나간다 → 가져가는 길이 cur 증가
• H 를 높게 잡을수록 → 덜 잘려 나간다 → 가져가는 길이 cur 감소

즉,
H 가 증가할수록 cur 은 단조 감소한다.

이런 “단조성”이 있으면 → 딱 이분 탐색 쓰기 좋다.

어떤 값 H에서 조건(cur >= target)을 만족하면,
그보다 작은 H에서도 항상 만족하고,
그보다 큰 H에서는 언젠가부터 만족하지 않게 된다.

이 구조 덕분에
“조건을 만족하는 H들 중 최댓값”을 이분 탐색으로 찾을 수 있다.

2. 이분 탐색 구간 설정

절단기 높이 H 의 가능한 범위는?

• 최소 높이: 1 (0으로 둬도 되지만, 실제로 0에서 자르는 건 의미가 없어서 1로 시작해도 OK)
• 최대 높이: max(trees) (가장 큰 나무보다 더 높게 설정해봐야, 전부 0 잘림)

그래서 코드에서:

• left = 1
• right = max(trees)

3. mid = 현재 절단기 높이

• mid = (left + right) // 2
• 이 mid 를 “절단기 높이 H 후보”라고 생각하고,
• 이 높이로 잘랐을 때 가져가는 나무의 총 길이 cur 를 계산해본다.

계산 방법:

• 각 나무 높이 tree 에 대해
  • cut = tree - mid
  • 만약 cut < 0이면 → 잘릴 수 있는 게 없으니 0으로 처리
  • cur += cut

이렇게 전체 나무에 대해 cur 을 구하면,

• cur >= target 이면 → “너무 많이 or 딱 맞게 가져가는 중”

  • 즉, 절단기 높이를 더 높여도 target을 만족하는 가능성이 있다
  • 우리는 “최대한 높게” 자르는 답을 원하니,
    • answer = mid 로 갱신 (현재 mid는 최소한 유효한 답)
    • left = mid + 1 로 오른쪽 구간 탐색

• cur < target 이면 → “목표보다 부족”

  • 절단기 높이를 너무 높게 잡은 것
  • 더 낮춰야 많이 잘릴 수 있음 → right = mid - 1

4. 답이 갱신되는 위치

cur >= target 인 구간에서만 answer 를 갱신한다.

• 왜냐면, 목표 이상으로 잘라야만 “조건을 만족하는 H”이기 때문.
• 그 중 가장 큰 H 를 찾기 위해,
  • 조건을 만족할 때마다 answer = mid 해주고
  • 더 큰 H를 찾으러 left = mid + 1 로 이동한다.

이분 탐색이 끝났을 때의 answer 가
조건을 만족하는 최대 절단기 높이가 된다.

해답 및 풀이

iimport sys
input = sys.stdin.readline

# N : 나무의 수 , target : 목표 길이
N, target = map(int,input().split())

trees = list(map(int,input().split()))

# 자르려는 나무의 길이와 가져가는 나무의 길이의 관계가 단조적이다.
# 고로 이분탐색이 가능하다.

answer = 0

left = 1 # 높이의 최솟값
right = max(trees) # 높이의 최댓값

while left <= right:
    mid = (left+right) // 2
    
    cur = 0 # 현재 가져가는 나무의 길이

    for tree in trees:
        cut = tree - mid
        if cut < 0:
            cut = 0
        cur += cut
        
    # 가져가는 나무 길이가 목표 이상이면
    # -> 더 높게 잘라도 되는지 시도
    if cur >= target:
        answer = mid
        left = mid + 1
    # 가져가는 나무 길이가 부족하면
    # -> 절단기 높이를 낮춰야 함
    else:
        right = mid - 1

print(answer)

어떤 기준값을 정했을 때 조건을 만족하는지/아닌지 판별할 수 있고
그 기준값에 대해 단조성이 있을 때
바로 파라메트릭 서치(이분 탐색)로 가져갈 수 있다.

---

    for tree in trees:
        cut = tree - mid
        if cut < 0:
            cut = 0
        cur += cut

에서 mid가 tree보다 큰 경우 음수가 나오니까 음수일때는 0으로 초기화 하는 코드

조금 더 세련되게 쓰고 싶다면

cur += max(tree - mid, 0)

이런 방법이 있었다. max() 함수를 기억하기