나무 자르기 성공다국어
| 1 초 | 256 MB | 98580 | 28463 | 17635 | 25.593% |
문제
상근이는 나무 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미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.
예제 입력 1 복사
4 7
20 15 10 17
예제 출력 1 복사
15
예제 입력 2 복사
5 20
4 42 40 26 46
예제 출력 2 복사
36
출처
Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #5 2번
- 문제를 번역한 사람: baekjoon
- 데이터를 추가한 사람: csehydrogen, jh05013, upple1
- 문제의 오타를 찾은 사람: jongseo_park
- 빠진 조건을 찾은 사람: rdd6584
- 잘못된 데이터를 찾은 사람: tncks0121
import sys
sys.setrecursionlimit(10000)
def binary(start, end, M):
if start >= end:
return start
mid = (start+end) // 2
total = 0
for i in lst:
if mid < i:
total += i - mid
if total < M:
return binary(start, mid-1, M)
elif total > M:
return binary(mid+1, end, M)
else:
return mid
if __name__ == '__main__':
tree, M = list(map(int,input().split()))
lst = list(map(int, input().split()))
print(binary(1, max(lst), M))처음에는 재귀를 이용해서 코드를 구성하였으나 시간 초과로 오류가 발생했다. 재귀를 사용할 때 처음에
binary(start, mid-1, M) 과 같이 return을 하지 않고 함수를 호출했는데 이렇게 하면 return 값이 없으므로 None이라는 값이 반환되므로 다음과 같이 return을 쓰는 것을 잊지말자 -> return binary(start, mid-1, M)
import sys
if __name__ == '__main__':
tree, M = list(map(int,input().split()))
lst = list(map(int, sys.stdin.readline().split()))
start = 1
end = max(lst)
while start <= end:
mid = (start+end) // 2
total = 0
for i in lst:
if mid < i:
total += i - mid
if total < M:
end = mid -1
elif total > M:
start = mid + 1
else:
break
print(mid)재귀가 아닌 while을 써서 코드를 작성하면 문제가 해결될 줄 알았으나 코드를 제출하면 시간초과가 아닌 그냥 틀렸다고 하는데 어디서 틀렸는지 잘 모르겠다.
import sys
if __name__ == '__main__':
tree, M = list(map(int,input().split()))
lst = list(map(int, sys.stdin.readline().split()))
start = 1
end = max(lst)
while start <= end:
mid = (start+end) // 2
total = 0
for i in lst:
if mid < i:
total += i - mid
if total < M:
end = mid -1
elif total >= M:
start = mid + 1
print(end)가장 문제는 total이랑 M이 같을 경우 어떻게 처리할지 잘 생각해야 한다. total이 M과 같은 경우 두 가지 선택을 해야한다.
total <= M 처럼 조건을 만드는 경우 total이 M과 같을 때 total이 커지는 방향으로 가므로 목표보다 커진다.
total >= M 처럼 조건을 만드는 경우 total이 M과 같을 때 total이 작아지는 방향으로 가므로 목표보다 작아진다.
total이 M과 같을 수 있다면 아마 두 조건 무엇을 선택해도 같은 결과를 내놓을 것이다. 하지만 total이 M과 정확하게 같지 않은 경우를 고려해야 한다. 정확하게 어떤 경우로 인해 오류가 나는지 잘 모르겠지만 조건에 만족하지 않는 쪽에 있다가 마지막에 mid -1 이나 mid + 1로 인해 조건이 만족하도록 하면 어떤 경우든 실패하지 않으므로 total >= M 처럼 조건을 만들어야 한다.
아직 정확하게 문제점을 몰라서 일단 경험적으로 외워버렸다.
댓글