[백준알고리즘] 2805번: 나무 자르기 -Python

[백준알고리즘] 2805번: 나무 자르기 -Python

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

2805번: 나무 자르기

20200418 아래에 새로 푼 코드를 추가했다.

---

이분 탐색 문제이다. 이전에 풀었던 이분 탐색 문제와 크게 다르지 않다.

 

다만 이전과 다르게 중간값을 구할 때 버림한 값이 아닌 올림한 값을 잡기 위해 2로 나누기 전에 +1을 해주었다. 이렇게하면 변수를 하나 더 두어서 최적의 값을 저장하고 있지 않아도 탈출 조건을 만족시켜 탈출할 수 있게 된다.

 

다른 분들의 코드를 보니 물론 변수를 하나 더 두고 전형적인 Binary Search 방식으로 min~mid-1, mid+1~max로 탐색을 수행하시는 분들이 많았다. 이외에도 bisect를 통해 mid값이 위치할 수 있는 인덱스를 찾는 방법을 사용하신 분도 계셨다. counter를 이용하시고 lowest범위를 highest-M으로 줄이신 분의 코드는 다른 분들에 비해서 혁신적으로 빨라서 놀랐다.... counter를 이용해서 sun(list)형태로 값을 구하셨는데.. 백준에서 본 코드라 나중에 확인을 또 해야겠다.

 

import sys

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

def solve():
	lowest, highest = 0, max(trees)

	while lowest != highest:
		middle = (lowest + highest + 1)//2
		bring = sum([(h - middle if h > middle else 0) for h in trees])

		if bring >= M:
			lowest = middle
		else:
			highest = middle - 1

	return highest

sys.stdout.write(str(solve()))

 

20200418

오늘은 이분탐색을 적용한 재귀로 풀어봤다. 반복문으로 푸는 방식도 해봤지만 위의 코드와 아래코드를 섞은 거라 따로 올리진 않는다.

 

재귀로 풀 때는 가장 낮게 자를 수 있는 높이와 가장 높게 자를 수 있는 높이를 인자로 넘겨주었고, 둘의 중간값을 구했다.

여기서 중간 높이를 구할 때에는 (l+h+1)//2가 아닌 (l+h)//2로 잡아주었다. 그래서 탈출조건으로 l과 mid가 같아지는 경우를 처리해주었다. l과 h가 1차이가 날 때를 의미하는데, 이때 h로 m이상의 나무를 구하느냐 못하느냐에 따라서 높이를 h와 l을 구분할 수 있다.

import sys

def solve(l, h):
    mid = (l + h)//2
    if l == mid:
        return h if sum(map(lambda x: x-h if x > h else 0, tree)) >= m else l

    cut = sum(map(lambda x: x-mid if x > mid else 0, tree))
    if cut == m: return mid
    elif cut < m: return solve(l, mid-1)
    else: return solve(mid, h) # cut > m

n, m = map(int, sys.stdin.readline().split())
tree = list(map(int, sys.stdin.readline().split()))
low, high = 0, max(tree)
print(solve(low, high))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다