문제링크
문제 설명
- 문제설명 :
일렬로 있는 나무들을 한꺼번에 자를 때 절단기 위치보다 높은 나무들만 잘릴 것이고
낮은 나무들은 잘리지 않을 것이다.
만약 M미터의 나무를 가져가고 싶다면 절단기를 놓을 위치를 구하랑
주제
- 이분탐색
난이도
- 중
풀이 전 생각한 것
- 톱날의 높이가 낮을 수록 더 많은 나무를 벨 수 있다.
- 문제 '톱날의 높이'를 Binary Search를 이용하여 찾아 나간다.
- 톱날의 높이가 결정되었을 때, height 미터보다 크거나 같으면, 톱날의 높이 cutter를 높여준다. (같을 때 톱날의 높이를 높여주는 것이 핵심.)
- M미터보다 작으면, 톱날의 높이 H를 낮춰준다.
참고 출처
1차 풀이 (선형 탐색)
import sys
count, length_required = map(int, input().split())
trees = list(map(int, sys.stdin.readline().split()))
trees.sort()
# 가운데 나무를 기준으로 시작
mid_index = count // 2
cutter = trees[mid_index]
height = 0
while True:
height = 0
for tree in trees:
n = tree - cutter
if n >= 0:
height += n
# 만약 절단된 나무가 요구된 길이보다 짧다면 절단 높이를 낯줘준다.
if height < length_required:
cutter -= 1
# 만약 절단된 나무가 요구된 길이보다 길다면 절단 높이를 높혀준다.
elif height > length_required:
cutter += 1
# 절단된 나무길이와 요구된 나무길이가 동일할 때 까지 반복한다.
if height == length_required:
break
print(cutter)
1차 풀이 방법
1차 풀이는 선형 탐색을 이용해서 풀었다. 절단된 나무 길이와 절단기 위치를 비교해가며
둘의 값이 동일해질 때까지 절단기의 위치를 1씩 조절해갔다.
결과적으로 시간복잡도가 높아 '시간초과'가 걸려 통과하지 못했다.
애초에 이분탐색문제를 선형탐색으로 진행했으니 당연한 결과이긴하지..
2차 풀이 (이진 탐색)
import sys
count, length_required = map(int, input().split())
trees = list(map(int, sys.stdin.readline().split()))
start = 0
end = max(trees)
# '시간초과'를 방지하기 위해 while문에 포함하지않고 함수를 따로 빼놓음
# 절단기 높이 구하는 함수
def tree_height(cutter):
height = 0
for tree in trees:
if tree - cutter > 0:
height += (tree - cutter)
return height
while start <= end:
cutter = (start + end) // 2
height = tree_height(cutter)
print(f'start: {start}, end: {end}, cutter: {cutter}, height: {height}', 'test')
# 만약 절단된 나무가 요구된 길이보다 짧다면 절단기를 놓을 범위를 낮춰준다.
if height < length_required:
end = cutter - 1
# 만약 절단된 나무가 요구된 길이보다 길다면 절단기을 놓을 범위를 늘려준다.
elif height >= length_required:
answer = cutter
start = cutter + 1
# 절단된 나무길이와 요구된 나무길이가 동일할 때 까지 반복한다.
if height == length_required:
break
print(answer)
2차 풀이 방법
2차 풀이로는 이진 탐색을 사용했다. input값을 받는 부분부터 while문까지 전체적인 틀은
1차 풀이와 비슷하지만 절단기의 위치를 1씩 변경하는 것이 아닌 범위자체를 변경하여
위치를 찾을 수 있도록 진행하였다. 탐색하는 횟수가 확실히 줄어드니 시간복잡도도 낮아져
시간초과 없이 통과할 수 있었다.
문제를 풀고 알게된 개념 및 소감
- 이론, 아무리 공부해봤자(많이 하진 않았지만) 내가 언제 써야할지 모르면 쓸모가 없다.
이진탐색은 다른 자료구조에 비해 간단해서 잘 알고 있다고 생각했는데, 막상 응용해보려니
막히는 부분이 많았다. 아직 100% 이해하지 못했다는 의미겠지..
자료구조를 이론만 아는 것이 아닌 문제에 응용할 수 있는 날이 언젠가 오길 바란다..
Learn From Yesterday, Live Today, Hope for Tomorrow