[BOJ - 이분탐색] 16564번 : 히오스 프로그래머 ( python )

 

백준 알고리즘 16564 히오스 프로그래머 파이썬

https://www.acmicpc.net/problem/16564

16564번: 히오스 프로게이머

 

 

문제

성권이는 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. 사고하기

• 목표 :  팀 목표레벨 T 
• 유형 : 이분탐색

먼저 내가 아이패드에 메모하며 사고를 한 과정을 공유한다.

 

- 목표레벨 T는 k를 여러명에게 나눠서 더해주었을 때, 가장 큰 mid값이다.

- start = 팀의 캐릭터 레벨 중 가장 작은 값

- end = 팀의 캐릭터 레벨중 가장 작은값에 k를 더해준 값. 

- 일반적인 이분탐색과 같이 조건은 while (start<=end)로 설정해주고 mid = (start + end) // 2를 해주었다. 

mid의 값이 팀 목표레벨이라고 생각하면, 

 

각 레벨이 10, 20 15일떄

팀목표레벨이 15이면 >> 5, 0, 0 로 되어 총 올린 레벨은  5인 것을 확인할 수 있다. 

 

mid값보다 현재레벨이 작으면   ->  hap 이라는 변수에 (mid - 레벨)을 더해줌으로써 총 올린레벨을 구해줬다. 

* (mid - 레벨) : 팀목표레벨이 mid일 때 각캐릭터가 몇레벨을 올렸는지

 

만약 총 올린레벨 hap 이 k보다 작거나 같을경우 start 를 mid+1설정, res 라는 변수에 max(mid, res)해주어서 mid값중 가장 큰값을 구해주었다. 

else :일 경우 >> 총 더한 레벨이 k보다 큰 값이므로 정답이 될 수 없어 res설정이 불가하고, end 만 mid-1로 설정해 k를 줄여주면 끝

 

 

 

2. 이 문제를 공유한 이유

- 이분탐색의 출력조건

나는 이분탐색 문제를 풀면서 한가지 깨달은 게 있다. 

기본적인 이분탐색에서 요구하는 값은 항상 mid값중 최대이거나, 최소인 값들이라는 점이다. 

 

그렇다는건 문제의 출력과 mid를 연결해서 생각하면 좀더 쉽게 생각할수 있다는 것.!!!!

나는 목표레벨 T가 결국 k를 여러명에게 나눠서 더해주었을 때, 가장 큰 mid값이라고 생각했다.

 

- start와 end의 조건을 생각하는 방법 

위에서 mid는 어떤값인지 명확하게 정의했다. 

그렇다면 mid를 만들기 위한 start와 end는 어떻게 파악해야할까.

 

위에 아이패드 메모에 적어놨는데 나는 각 레벨을 선으로 그렸다.

 

그리고 T의 최소값은 mid(levels)라고 생각했다. 

start를 가장 작은값보다 작게 만들면 (예를들면 1) mid값이 계산 중에 가장 작은 값보다 작아질 가능성이 생기고, 

그러면 k를 더한게 아닌 값이 된다. (위에서 정의했듯, mid는 k를 여러명에게 나눠서 더해줬을때의 값이다.)

 

그렇다면 최대값은 무엇일까?

최대값은 최소값에 k를 더한 값이면 충분하다. (k를 한명한테 몰빵해서 줄 가능성도 있기 때문)

 

 

 

정답코드

#16564_히오스 프로그래머_binary search_silver1

import sys
input = sys.stdin.readline

n, k = map(int,input().split())
levels = [ int(input()) for _ in range(n)]

start = min(levels)
end = start + k

res = 0
while start <= end:
    mid = (start + end) // 2
    
    hap = 0
    for level in levels:
        if mid > level:
           hap+= (mid - level)
           
    if hap <= k:
        start = mid+1
        res = max(mid,res)
    else:
        end = mid -1


print(res)