2805번: 나무 자르기
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보
www.acmicpc.net
아이디어: 이분탐색
이분탐색을 이용하여 푸면 된다. 하지만, 구현 과정에서 그냥 mid 값을 출력하니 틀렸다. 조금만 생각해보면 당연한 것이다. 조건에 맞을 경우에만 답을 업데이트해주고 그 답을 출력해야 한다.
그런데 또 파이썬으로 제출하면 시간초과가 떠서 pypy로 제출했는데, 질문을 보니 시간을 단축할 수 있는 방법을 생각해보라고 해서 이왕 정렬하는 거 배열의 끝에서 부터 비교를 해서 만약 i<m이면 그 앞의 것들은 비교하지 않고 넘어갈 수 있지 않을까 생각했다. 실패다.. 오히려 시간이 더 늘어났다.. ^^
일단 이건 변경 전 코드이다. 파이썬 시간초과 pypy통과
#이분 탐색
import sys
n, m = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
arr.sort()
left = 0
right = arr[-1]
ans = 0
while (left<=right):
mid = (left+right)//2
result = 0
for i in arr:
if (i>mid):
result += i-mid
if (result>=m):
left = mid + 1
ans = max(ans, mid) ##주의! 그냥 mid를 출력하면 답을 구할 수 없다.
else:
right = mid - 1
print(ans)
그리고 이건 시간단축 실패한 코드..
#이분 탐색
import sys
n, m = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
arr.sort()
left = 0
right = arr[-1]
ans = 0
while (left<=right):
mid = (left+right)//2
result = 0
#시간을 줄이기 위한 방법..? 배열의 모든 원소를 비교하지 않아도 되도록.
for i in range (n-1, -1, -1):
if (arr[i]>mid):
result += arr[i]-mid
else:
break
if (result>=m):
left = mid + 1
ans = max(ans, mid) ##주의! 그냥 mid를 출력하면 답을 구할 수 없다.
else:
right = mid - 1
print(ans)
'알고리즘💻 > 이분탐색&정렬&분할정복' 카테고리의 다른 글
BOJ 10825번: 국영수 (0) | 2021.07.18 |
---|---|
BOJ 18870번: 좌표 압축 (0) | 2021.05.05 |
BOJ 3758번: KCPC (0) | 2021.01.29 |
BOJ 1181번: 단어 정렬 (0) | 2021.01.29 |
BOJ 1026번: 보물 (0) | 2021.01.29 |