[백준] 16564 히오스 프로게이머

문제

• 성권이는 게임이 끝날 때까지 총 K개의 레벨을 올릴 수 있다.
• N개의 캐릭터의 현재 레벨이 주어질 때, 캐릭터의 최소 레벨을 최대로 하기

 

• 1 <= N <= 1,000,000
  1 <= K <= 1,000,000,000

 

풀이

• 최소 레벨의 캐릭터를 최대로 올려야 한다.
• 정렬 후, 최대 K만큼 최소 레벨의 캐릭터를 그 다음 캐릭터의 레벨만큼 올려준다.
  • idx =0 으로 시작해서, 0번 레벨과 1번 레벨의 차이가 K보다 작다면 그만큼 올려준다.
  • idx =1, 2번 레벨과 1번 레벨 * 2(0번과 1번 모두 올려야 함) 차이가 K보다 작다면 그만큼 올려준다.
  • ...
  • idx =n, n+1번 레벨과 n번 레벨 * (n+1) 차이가 K보다 크거나 같다면, 모든 캐릭터를 n번 레벨로 만들 수 없으므로
    K // n 만큼씩 올려주도록 한다.
  • 만약 모든 캐릭터의 레벨이 동일한데 K가 남는 경우에도, K // N 만큼씩 올려준다.

 

N, K = map(int, input().split())
levels = [int(input()) for _ in range(N)]
levels.sort()
idx = 0

while K > 0 and idx < N:
    if idx == N-1 : # 마지막 인덱스까지 도달한 경우
        levels[idx] += K // N
        break
    
    gap = (levels[idx+1] - levels[idx]) * (idx+1)
    if gap >= K :
        levels[idx] += K // (idx+1)
        K = 0
    else :
        idx += 1
        K -= gap

print(levels[idx])

 

References

• 백준 오늘의 문제