[백준] 2805. 나무 자르기

문제

• 절단기의 높이를 정할 수 있다. 절단기의 높이보다 높은 나무들은 잘리고, 낮은 나무들은 가만히 있는다
• 예를 들어, 절단기의 높이가 15인데 나무가 17 18 15 3 이면 나무들은 15 15 15 3이 되어서 2, 3, 0, 0개 -> 5m를 얻을 수 있다.
• 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최대값은 무엇인가?

접근

1. 잘못된 접근

나무의 개수는 N, 상근이가 가지고 가려는 나무의 길이는 M, prev_gap = 100
일단 1부터 나무들의 높이의 최댓값까지를 반복문 돌린다.
만약, 1일 때
나무를 자름 
여기서도 나무의 개수만큼 반복문을 돌린다. (20 15 10 17)
첫 번째 나무 - 1 -> 19
두 번째 나무 -1 -> 14
세 번째 나무 -1 -> 9
네 번째 나무 -1 -> 16
=> 19 + 14 + 9 + 16 만큼의 나무를 얻음
=> 만약, 얻은 나무의 길이-M이 0보다 크고 prev_gap보다 작다면 갱신해줌

-> 나무가 제일 작게 남을 때를 구하는 줄 알고 했던 접근 방식

2. 두 번째 접근

나무의 개수는 N, 상근이가 가지고 가려는 나무의 길이는 M

일단 나무들의 높이에서 0까지를 반복문 돌린다. (20 15 10 17)
만약, 20일 때 / 나무의 높이가 20보다 큰 지 작은 지 비교
첫 번째 나무 - 20 -> 0
두 번째 나무(작음)
세 번째 나무 (작음)
네 번째 나무 (작음)
=> 0m
만약, 나온 길이가 M보다 길다면 return

N, M = list(map(int, input().split()))

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

for i in range(max(tree_length_list)):
    sum_length = 0
    for tree_length in tree_length_list:
        if(tree_length > max(tree_length_list)-i):
            sum_length += tree_length-(max(tree_length_list)-i)
        
    if(sum_length >= M):
        answer = max(tree_length_list) -i
        break

print(answer)

-> 시간초과

• max(tree_length_list)를 계속 써줘서 그런가? 하고 변수로 바꿔줌 -> 이래도 시간초과
• 상근이의 나무 길이 최대 값이 2,000,000,000인 거 확인 -> 이분 탐색으로 풀어보자!

3. 세 번째 접근

min과 max의 중간값으로 설정한다.(10)
10일 때,  만약, 나무 높이가 중간값보다 크면?  10, 5, 0, 7 -> 22
만약 7을 바로 찾았다면, return mid
22개가 7보다 크다면?
	min을 10으로 저장,
	min과 max의 중간 값으로 감
	
15일 때, 만약 중간값이 나무 높이보다 크다면? 5, 1 -> 6
6이 7보다 작다면?
	max를 15로 저장,
	min과 max의 중간 값으로 감

13일 때, 7, 2, 3 -> 12 큼
	min을 13으로 저장

14일 때, 6, 1, 2 -> 9 큼
	min을 14로 저장

If(min==max): return min

N, M = list(map(int, input().split()))

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

min = 0
max = max(tree_length_list)

while(min<=max):
    mid = round((min+max)/2)

    sum_length = 0
    for tree_length in tree_length_list:
        if(tree_length > mid):
            sum_length += tree_length-mid

    if(sum_length==M):
        break

    elif(sum_length>M):
        min = mid

    elif(sum_length<M):
        max = mid

    else:
        break

print(mid)

-> 또 시간초과 .. 왜?
-> sys가 아니라 input() 써서 그런가? -> 시간초과
-> if문들 순서를 바꾸어줘야 하나? -> 시간 초과

아무리 생각해도 모르겠다...

다른 사람 코드

import sys

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

tree_length_list = list(map(int, sys.stdin.readline().split()))

min = 0
max = max(tree_length_list)

while(min<=max):
    mid = (max + min) // 2

    sum_length = 0
    for tree_length in tree_length_list:
        if(tree_length > mid):
            sum_length += tree_length-mid

    if(sum_length>=M):
        min = mid + 1

    else:
        max = mid - 1

print(mid)

-> 성공 뜨는데 도대체 뭐가 다른 거지!!

**

• if문 순서도 같게 해줬는데 아니다..

import sys

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

tree_length_list = list(map(int, sys.stdin.readline().split()))

min = 0
max = max(tree_length_list)

while(min<=max):
    mid = (max + min) // 2

    sum_length = 0
    for tree_length in tree_length_list:
        if(tree_length > mid):
            sum_length += tree_length-mid

    if(sum_length>=M):
        min = mid

    else:
        max = mid

print(mid)