백준 2512 예산 Python

🐸 문제 정보

2512번: 예산

 

🤖 알고리즘

이분탐색

(이지만 나는 그리디로 풀었..다)

 

⏱️ 풀이 시간

10.58m

 

📝 풀이

유형은 이분 탐색이었지만, 문제를 봤을 때 이분탐색보다 그리디가 먼저 떠올랐다.

이분탐색 풀이도 아래에 있다.

 

1. 입력 값을 오름차순으로 정렬
2. (현재까지 남은 값 / 남은 인원)과 현재 보고있는 값을 비교한다
3. 만약 현재 보고 있는 값이 더 작다면, 예산 최대 값에서 현재 보고 있는 값을 빼고 res와 뺀 값을 비교한다
4. 반대의 경우, (현재까지 남은 값 / 남은 인원)을 res와 비교하고 순회를 break 한다.

 

🧑‍💻 나의 답

그리디

# pypy3

import sys
import math
input = sys.stdin.readline

n = int(input().rstrip())
nums = sorted(list(map(int, input().rstrip().split())))
val = int(input().rstrip())
res = -sys.maxsize

for i in range(n):
    avg = math.floor(val / (n - i))
    if nums[i] < avg:
        val -= nums[i]
        res = max(res, nums[i])
    else:
        res = max(res, avg)
        break

print(res)

 

이분탐색

# pypy3

import sys
input = sys.stdin.readline

n = int(input().rstrip())
nums = list(map(int, input().rstrip().split()))
val = int(input().rstrip())

start, end = 0, max(nums)
while start <= end:
    mid = (start + end) // 2
    total = 0
    for num in nums:
        if num > mid:
            total += mid
        else:
            total += num
    if total <= val: start = mid + 1
    else: end = mid - 1

print(end)

 

위에가 이분탐색, 아래가 그리디

결과는 어째 놀랍도록 똑같다.

오히려 그리디가 메모리는 더 적게 사용했다.