2805번: 나무 자르기
https://www.acmicpc.net/problem/2805
문제 정의
상근이는 M미터의 나무가 필요해서 나무를 벌목하려고 한다.
절단기의 높이를 설정하면, 높이만큼 나무를 잘라주는데, 나무들의 높이가 주어졌을 때 적어도 M미터의 나무를 가져가려면 절단기의 높이를 최대 몇까지 설정할 수 있을까?
접근 방법
- 나이브한 접근방법
- 나무리스트 [20, 15, 10, 17] 가 주어졌을 때, 절단기의 높이를 1~최대 나무 높이(=20)까지 설정해보면서, (나무-절단기높이)의 합이 M미터 이상인지 확인하면 된다.
- 즉,
sum(각 나무높이 - 절단기 높이) ≥ M(적어도 M 미터이므로, M이상과 비교하면 된다.)
- 하지만, N은 최대
2,000,000,000이므로, 이중 for문을 사용하면 시간 초과가 발생한다.
- 따라서 순차적 탐색보다는 좀 더 효율적인 탐색이 필요하다.
- 효율적인 탐색: 이진탐색 활용하기
- 절단기에 설정할 수 있는 높이를 탐색할 때, 1 ~ 최대 나무 높이 까지 모두 확인하지 않아도 된다.
[20, 15, 10, 17]나무 리스트가 있을 때, 상근이가 적어도 7M의 나무를 원한다면,sum(각 나무높이 - 절단기 높이)가 7M 미만이 되는 절단기 높이는 보지 않아도 되기 때문이다.
- 즉, 절단기 높이가 15일 때, 상근이는 총 7m를 들고 갈 수 있는데, 예를 들어 절단기 높이가 16이라면, (4+1 = 5)로 7M보다 더 적은 나무를 얻게 되므로 16부터는 계산하지 않아도 된다.
- 따라서 적절한 기준을 설정한 후 그 기준에 따라서 탐색할 범위를 좁혀나간다면 시간 복잡도를 으로 줄일 수 있게된다.
문제 해설
이진 탐색을 사용할 때는 start와 end를 설정하는 것이 중요하다.
이 문제에서는 start는 1, end는 최대 나무 길이로 설정할 수 있다.
또한 이진 탐색을 할 땐 반드시 탐색하고자 하는 배열을 정렬해야한다.
정렬이 완료된 배열을 이진탐색하면 된다.
이 때 찾고자 하는 타겟을 mid로 설정하고 sum(각 나무높이 - mid) 로 얻을 수 있는 나무를 계산한 뒤에 이 값이 상근이가 원하는 M보다 크거나 같으면, 그 mid가 답이 된다.
[주의할 점]
- 문제에서 상근이는 적어도 M미터 이상의 나무를 가져간다고 했다. 따라서 자른 나무의 합이 꼭 M이 아닐 수도 있다는 이야기이다. (=M이상이라는 말)
- 이 점에 유의해서 이진 탐색의 조건을 잘 설정해야 한다.
- 구체적인 예시
4 8
20 15 10 17
# 답은 14
풀이
시간 초과 코드
- 이분 탐색을 구현했지만, mid가 리턴되는 조건을 잘못 설정해 시간 초과가 떴다.
- 그리고 M이어야만 mid를 출력하는 것으로 구현했기 때문에 예외 상황이 있었다.
import sys
input = sys.stdin.readline
N, M = map(int, input().split()) # N(나무의 수), M(가져가려고 하는 나무 길이)
tree = sorted(list(map(int, input().split()))) # 나무 리스트
# 1~20(나무 최대 길이)
# 10(10+5+7 = 22) -> M 보다 크면, 더 많이 잘라야 하므로, 10 이후에서 다시 찾기
# 15(5+2 = 7)
def binary_search(tree, M, start, end):
sum = 0
if start > end:
return binary_search(tree, M+1, end-1, start-1)
mid = (start+end) // 2
for t in tree:
if t-mid >= 0: # 잘라진다면,
sum += (t-mid)
if sum == M:
return mid
elif sum > M:
return binary_search(tree, M, mid+1, end)
else:
return binary_search(tree, M, start, mid-1)
result = binary_search(tree, M, 0, max(tree))
print(result)
올바른 코드
- 예외 상황을 포함해 조건문을 ≥ 로 수정하니 시간 초과도 나오지 않았다.
import sys
input = sys.stdin.readline
N, M = map(int, input().split()) # N(나무의 수), M(가져가려고 하는 나무 길이)
tree = sorted(list(map(int, input().split()))) # 나무 리스트
def binary_search(tree, M, start, end):
sum = 0
mid = (start+end) // 2
if start > end:
return mid
# 나무 자르기
for t in tree:
if t-mid >= 0: # 잘라진다면,
sum += (t-mid)
if sum >= M:
return binary_search(tree, M, mid+1, end)
else:
return binary_search(tree, M, start, mid-1)
result = binary_search(tree, M, 0, max(tree))
print(result)
정리
- 시간 복잡도는 이다.
- 이분 탐색을 공부했다면 쉽게 아이디어를 파악할 수 있는 문제였다.
- 하지만 이분 탐색 구현에서 자주 실수 할 수 있는 시작점, 끝점 설정과 리턴 조건을 꼼꼼하게 확인할 필요가 있었다.
Uploaded by N2T
