백준_16564_히오스 프로게이머(python)

※ 접근법

 처음에는 데이터 갯수가 너무 많아서 그리디이지 않을까 떠올렸다. 근데 그리디라고 하기에는 탐욕적인 방법이 떠오르지 않았다. 그래서 힙을 이용하여 heappop을 통해 최솟값을 계속 꺼내서 값을 구할까도 생각을 해봤지만 결국 구해나가는 방법이 그리디적으로 생각을 해야했고 발상이 떠오르지 않았다. 그래서 다른 알고리즘이 없을까 하다가 이분탐색을 떠올렸다.

 

  ※ 풀이

1. 각 캐릭터의 레벨을 입력 받으면서 최소 레벨과, 최대 레벨을 구해준다. (최종적으로 코드에서는 최대 레벨을 사용하지 않았지만 처음에는 혹시 모르니 구해놨다.)

2. 최소 레벨을 맞추기 위해 높은 레벨이 낮아질 필요는 없으니 데이터를 올림차순으로 정렬시켰다.

3. 이분탐색 로직에서는 mid값보다 커지는 구간이 나오면 반복문을 종료시켰다.

import sys
input = sys.stdin.readline

n,k = map(int,input().split())

data = []

min_num = float("inf")
max_num = 0

for i in range(n):
    num = int(input())
    data.append(num)
    min_num = min(min_num, num)
    max_num = max(max_num,num)

data.sort()

left, right = min_num, min_num + k
result = 0
while left <= right:
    mid = (left + right) // 2
    temp = 0
    for i in data:
        if i > mid:
            break
        temp += mid - i
        if temp > k:
            break
    if temp > k:
        right = mid - 1
    else:
        left = mid + 1
        result = mid

print(result)

※ 회고

 처음에 바로 이분탐색을 바로 떠올리지 못한 점이 아쉽다. 최근 그리디 알고리즘만을 푼 것은 아닌데 요즘에 뭔가 그리디 알고리즘에 매몰되있는 것 같다. 유연한 사고를 하자!!