문제

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	4546	1484	1026	34.383%

문제 설명

성권이는 Heroes of the Storm 프로게이머 지망생이다.

이 게임에는 총 N개의 캐릭터가 있다. 그리고 현재 각 캐릭터의 레벨은 Xi이다. 성권이는 앞으로 게임이 끝날 때까지, 레벨을 최대 총합 K만큼 올릴 수 있다.

팀 목표레벨 T =min(Xi) (1 ≤ i ≤ N)라고 정의하면, 게임이 끝날 때까지 성권이가 달성할 수 있는 최대 팀 목표레벨 T는 무엇인가?

예를 들어, N = 3, X1= 10, X2= 20, X3= 15이고 K = 10일 때, X1을 7만큼 올리고 X3을 2만큼 올리면 최소 레벨 Xi는 17이 된다. 따라서 팀 목표레벨 T는 17이다. 이 경우처럼 레벨을 총합 K보다 적게 올릴 수도 있다.

입력

첫째 줄에는 캐릭터의 개수 N, 올릴 수 있는 레벨 총합 K가 주어진다. (1 ≤ N ≤1,000,000, 1 ≤ K ≤ 1,000,000,000)

다음 N개의 줄에는 현재 각 캐릭터의 레벨이 X1, X2, X3, ... , Xn 으로 주어진다. (1 ≤ Xi ≤ 1,000,000,000)

출력

가능한 최대 팀 목표레벨 T를 출력한다.

예제 입력 1

3 10
10
20
15

예제 출력 1

17

---

내 풀이

# 16564번 실버1
# 히오스 프로게이머
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
level = [int(input()) for _ in range(n)]
level.sort() # 레벨 오름차순 정렬

# 최댓값, 최솟값 정의
start = level[0]
end = level[-1] + k

while start <= end:
    mid = (start+end)//2
    diff = 0 # 각 레벨별 증가하는 레벨의 총합
    
    for l in level:
        if l < mid:
            diff += mid - l # mid와 기본 level간 차이나는 값을 diff에 더해줌
    
    if diff <= k: # diff가 k보다 작을 경우, mid가 작다는 의미
        start = mid + 1
        result = mid # 이때 값을 충족했으므로 일시적으로 mid값 저장(문제에서는 k값보다 diff가 작거나 같아야함)
    else:
        end = mid - 1

print(result)

이진탐색 문제의 핵심은 초기 start, end를 찾고 if~else문의 구조를 짜는 것이다.

앞서 이진탐색 문제 두개 풀어봤다고 또 생각보다 빨리 이해됨.

사람은 배움과 적응의 동물 ...