BOJ 2805번: 나무 자르기

www.acmicpc.net/problem/2805

2805번: 나무 자르기

아이디어: 이분탐색

이분탐색을 이용하여 푸면 된다. 하지만, 구현 과정에서 그냥 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)