성능 요약
메모리: 259740 KB, 시간: 568 ms
분류
이분 탐색, 매개 변수 탐색
문제 설명
상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.
목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.
상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)
둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.
출력
적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.
문제풀이
- 나무를 자를때, 내가 원하는만큼의 나무를 자르지 못할 수도 있음
- 전체의 합을 구하는게 아닌, 자른 뒤의 합들을 구해야 함
TROUBLE SHOOTING
-
문제를 접한뒤 마인드맵을 그리며 코드를 점점 확장시켜 나갔다. 이분탐색 문제이기에, 기초적인 순차탐색으로도 해결할수 있는 문제라 생각했고, 출력값을 미리 설정해야겠다 생각해서 for 문을 통해 출력값을 미리 정했다. (주석참고!) 이게 가장 치명적인 실수였다.
함수형 코딩을 통해서 내가 정한 값을 계산한뒤 다시 가져오려고 했는데, 생각보다 쉽지 않았고, 더욱더 깊이 들어갈수록 새롭게 정하는 변수들도 늘어났고, 코드를 정리도 힘들만큼 여러 정보들을 담게 됐다. 그래서 다 지운뒤, while문 안에 그 조건을 담고, 연산한뒤 바로 적용할수 있도록 for문을 작성해 집어넣었다.
생각보다 오랜 시간을 이 트러블슈팅에 사용 했지만, 이분탐색 문제해결 방법중 한가지를 알게 된것 같아서 다행이였다… -
이분탐색의 기본 틀은 아래와 같다.
if total == m: result = mid break elif total > m: start = mid + 1이렇게 코드를 진행했을때, 백준 예제들은 풀렸지만, 백준을 통과하질 못해서, 혼자는 도저히 생각해낼수 없을것 같아, 나의 희망 chatgpt를 활용했다. 실제 답은 아래와 같다.
if total >= m: result = mid start = mid + 1이 코드는 같은높이의 나무들 속에서 1개만 선택해 1만큼 자를수 있는 상황이 아니다 라는것을 내포한다 볼수 있다. 나무는 소수점으로 자를수도 없기에, m을 넘는 최소한의 높이까지를 잘라야 하므로, result에 mid값을 계속 갱신하며 넣어주면서, 더 이상 반복할 수 없을때 까지(start = end) 반복해주는 방법이다.
나무와 같은 조건을 가지게 되는 다른 문제들에도 적용되는 알고리즘 이기에, 확실하게 짚고 넘어가길 잘한것 같다.
코드
#https://www.acmicpc.net/problem/2805
#나무 자르기
#2805
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
n_list = list(map(int, input().split()))
# def binary(arr, target, start, end):
# while start <= end:
# mid = (start+ mid) // 2
# if arr[mid] == target:
# return mid
# elif arr[mid] > target:
# end = mid - 1
# elif arr[mid] < target:
# start = mid + 1
# return None
# for i in range(n):
# k = n_list[i] - target#자르는 높이
# chai_list.append(k)
start = 0
end = max(n_list)
result = 0
while start <= end:
mid = (start + end) // 2
total = 0
for i in range(n):
chai = n_list[i] - mid
if chai > 0:
total = total + chai
# if total == m:
# result = mid
# break
# elif total > m:
# start = mid + 1
#적어도 m이상이라는 조건을 만족하기 위한 알고리즘!
#왜 m 이상일까?
if total >= m:
result = mid
start = mid + 1
elif total < m:
end = mid - 1
print(result)
# if n_list[mid] == target:
# ans[i] = n_list[i] -
# #자르는 높이를 여기서 출력해야하는데 뭐랑 같아질때 출력해야하지?
# #각각의 나무들을 자른뒤의 나머지값들을 합친게 m이랑 같아질때
# elif n_list[mid] < target:
# start = mid + 1
# elif n_list[mid] > target:
# end = mid -1
# for i in range(n):
# k = n_list[i] - target#자르는 높이
# chai_list.append(k)
# result = sum(chai_list)
# if result == m:
# print(target)