Python 백준 2805 나무자르기 / 이진탐색 알고리즘

Python 백준 2805 나무자르기 / 이진탐색 알고리즘

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

2805번: 나무 자르기

N, M = map(int, input().split())
tree = list(map(int, input().split()))
start, end = 1, max(tree)  # 이분탐색 검색 범위 설정
# 1을 시작, end를 나무 중 긴 길이
# 원하는 나무 높이

while start <= end:  # 적절한 벌목 높이를 찾는 알고리즘
    mid = (start + end) // 2 # 1~20중 나무 높이의 절반 값

    log = 0  # 벌목된 나무 총합
    for i in tree:
        if i >= mid: # 나무 리스트의 인덱스보다 나무높이 보다 클 때
            log += i - mid # 나무 - 나무 높이 => 즉 벌목된 부분

    # 벌목 높이를 이분탐색
    if log >= M: #위에서 구한 벌목된 나무값이 얻어야할 나무량보다 크다면
        start = mid + 1 #다시 구할 나무높이의 시작부분인 start를 조정해준다.
        # 왜냐하면 1~20중에 구하는거였는데, 벌목된 값이 더 얻어야할 나무량보다 더 크니까
        # 나무의 높이가 올라가면 벌목될 log값이 줄어들기 떄문이다.
    else:
        end = mid - 1
        # log가 M보다 작으면 즉 벌목된 나무값이 구해야할 나무값보다 작다면
        # end 즉 구해야할 끝 부분을 중간 부분에서 1만큼 빼서 재설정 해준다.
        # 그래야 mid=나무높이의 값이 줄어들면서 벌목될 log 값이 커지기 때문이다
print(end) # 나무의 최대높이인 end값을 출력해 준다.

---

N, M = map(int, input().split())
tree = list(map(int, input().split()))
start, end = 1, max(tree)  # 이분탐색 검색 범위 설정
# 1을 시작, end를 나무 중 긴 길이
# 원하는 나무 높이

 

N, M으로 나무와 벌목해야할 입력값을 받는다.

 

왜인지는 모르겠으나, map을 사용 안 하고 그냥 int로 값을 받아오면 오류가 뜬다..

 

tree는 나무의 수를 리스트로 받아온 변수다.

 

start, end는 구해야할 나무 높이를 이분탐색으로 정한 것이다.

 

예제의 경우엔 1~20이 될것이다. 1은 최소값, 20은 나무의 최대 길이.

 

제일 큰 나무인 20을 넘어가버리면 아무 나무도 자를 수 없기 때문이다.

 

while start <= end:  # 적절한 벌목 높이를 찾는 알고리즘
    mid = (start + end) // 2 # 1~20중 나무 높이의 절반 값

    log = 0  # 벌목된 나무 총합
    for i in tree:
        if i >= mid: # 나무 리스트의 인덱스보다 나무높이 보다 클 때
            log += i - mid # 나무 - 나무 높이 => 즉 벌목된 부분

while문을 이용하여 반복한다.

 

start값이 end값보다 크거나 같아지면 이미 구하고 싶은 수는 구했거나 이 안에는 없다.

 

mid의 변수를 start+end를 더하고 2로 나눈다. 이분탐색을 활용하기 위한 시작.

 

이제 1~20 중에 mid는 10이될 것이고, 이 10을 가지고 나무들을 잘라낸 값들을 구할거다.

 

 

    log = 0  # 벌목된 나무 총합
    for i in tree:
        if i >= mid: # 나무 리스트의 인덱스보다 나무높이 보다 클 때
            log += i - mid # 나무 - 나무 높이 => 즉 벌목된 부분

log로 임의의 변수를 만든다.

 

반복문을 사용해, 처음에 입력값으로 받은 list인 tree를 돌린다.

 

if

 

나무 리스트의 i번째가 구해야 할 나무 높이보다 클 경우

 

log에는 i번째 인덱스(tree의 i번째 인덱스) - mid(처음에 정한 구해야할 나무 높이)를 더해준다.

 

여기서 i번째 나무가 mid보다 왜 클 경우만 자르냐면, 높이가 tree의 i번째 보다 높다면 어차피 잘라낼 값이 아예 없기 때문이다.

 

 

    # 벌목 높이를 이분탐색
    if log >= M: #위에서 구한 벌목된 나무값이 얻어야할 나무량보다 크다면
        start = mid + 1 #다시 구할 나무높이의 시작부분인 start를 조정해준다.
        # 왜냐하면 1~20중에 구하는거였는데, 벌목된 값이 더 얻어야할 나무량보다 더 크니까
        # 나무의 높이가 올라가면 벌목될 log값이 줄어들기 떄문이다.
        
    else:
        end = mid - 1
        # log가 M보다 작으면 즉 벌목된 나무값이 구해야할 나무값보다 작다면
        # end 즉 구해야할 끝 부분을 중간 부분에서 1만큼 빼서 재설정 해준다.
        # 그래야 mid=나무높이의 값이 줄어들면서 벌목될 log 값이 커지기 때문이다
print(end) # 나무의 최대높이인 end값을 출력해 준다.

 

이분탐색을 이용해 구한 log값이 구해야할 값인 M보다 작으면, 중간지점이었던 mid에 1을 더해서 시작지점으로 바꿔준 후 다시 while문의 처음으로 돌아간다.

 

else의 경우는 반대로 돌아간다.

 

start가 end보다 같거나 커지면 while문을 탈출한다.

 

    if log >= M:
        start = mid + 1
        
    else:
        end = mid - 1

 

조건문의 탈출조건은 start가 커져야하는데, 무엇이 되든 start가 +1이 되나, end가 -1이 되나 결국은 start가 더 커질것이기 때문이다.