[백준] 16564 : 히오스 프로그래머

문제

막힌 부분

생각해봤던 부분은 캐릭터를 각각 카드(총 N개의 카드)라고 생각하고, 올릴 수 있는 레벨의 총 합인 K를 카드를 선택 가능한 횟수라고 보는 것이다.

예를 들어, N이 3이고 K를 10이라고 본다면, 캐릭터의 레벨이 각각 10, 20, 15라고 했을 때

10
15
20

이라는 카드를 가지고 있는 것이고, 10번 선택해서 선택받은 횟수만큼을 현재 레벨에 더하는 것이다. 이렇게 재귀를 돌려서 해보면, 최대 팀 목표레벨은 17이 된다.

구조

low와 high를 정하고 (low+high)/2를 mid로 정합니다. 이때 mid는 팀의 목표 레벨입니다.
이제 각 캐릭터들의 현재 레벨과 팀 목표 레벨을 비교하고, 팀 목표 레벨보다 캐릭터의 현재 레벨이 작은 경우, 그 차의 합을 구합니다.
이 합이 K보다 큰 경우에는 high를 mid로, 작거나 같은 경우에는 low를 mid로 이동시킵니다.
https://intrepidgeeks.com/tutorial/c-baijun-16564-hero-player

유사 문제

https://velog.io/@letsbebrave/백준-2110-공유기-설치

원래 코드

N, K = map(int, input().split())
level = sorted([int(input()) for _ in range(N)])

def cal(level, mid): # 레벨 리스트, 올릴 수 있는 레벨 총합, 팀 목표 레벨
    sum = 0
    for i in level:
        if i < mid: # 팀 목표 레벨보다 레벨이 적을 때
            sum += mid - i
    return sum
            
def bsearch(level):
    level.sort()
    start = level[0]
    end = level[N-1] + K # 가장 최댓값은 level 리스트 중 가장 큰 수 + 올릴 수 있는 레벨의 총합
    
    while start <= end:
        mid = (start + end) // 2 # mid : 팀 목표 레벨
        
        if cal(level, mid) <= K: # 팀 목표 - 현재 각 캐릭터의 레벨 차의 합 <= 올릴 수 있는 레벨의 총합
            start = mid + 1 # 수를 키워야 하므로 start를 크게 만들어주기 위해 start = mid 대입
        elif cal(level, mid) > K:
            end = mid - 1 # 수를 작게 해줘야 하므로 end를 작게 만들어주기 위해 end = mid 대입
    
    return mid

print(bsearch(level))

정답 코드

다음 반복문 시 mid가 변경될 수 있으므로 성립할 때 result 변수에 mid 값을 미리 넣어 두았더니 정답이 됐다.
다음에 성립하지 않을 때 그대로 mid값을 return 해주면 안되기 때문!!

참고로 mid 값은 여기서 팀 목표 레벨이다!
잘못된 팀 목표 레벨을 반환하지 않도록 미리 성립할 때 result 변수에 mid 값을 넣어두면 된다.

N, K = map(int, input().split())
level = sorted([int(input()) for _ in range(N)])

def cal(level, mid): # 레벨 리스트, 올릴 수 있는 레벨 총합, 팀 목표 레벨
    sum = 0
    for i in level:
        if i < mid: # 팀 목표 레벨보다 레벨이 적을 때
            sum += mid - i
    return sum
            
def bsearch(level):
    level.sort()
    start = level[0]
    end = level[N-1] + K # 가장 최댓값은 level 리스트 중 가장 큰 수 + 올릴 수 있는 레벨의 총합
    result = 0
    while start <= end:
        mid = (start + end) // 2 # mid : 팀 목표 레벨
        
        if cal(level, mid) <= K: # 팀 목표 - 현재 각 캐릭터의 레벨 차의 합 <= 올릴 수 있는 레벨의 총합
            result = mid # 다음 반복문 시 mid가 변경될 수 있으므로 될 때 result 변수에 mid 값을 넣어줌
            start = mid + 1 # 수를 키워야 하므로 start를 크게 만들어주기 위해 start = mid 대입
        elif cal(level, mid) > K:
            end = mid - 1 # 수를 작게 해줘야 하므로 end를 작게 만들어주기 위해 end = mid 대입
    
    return result

print(bsearch(level))

22.04.12 다시 풀어보기

import sys

N, K = map(int, sys.stdin.readline().split())
level = sorted([int(sys.stdin.readline()) for i in range(N)])

def bsearch(level):
    start = 0
    end = level[-1] + K
    
    while start <= end:
        mid = (start + end) // 2 # 팀 목표 레벨
        sum = 0
        for i in level:
            if i < mid:
                sum += mid - i
        
        if sum > K: # 충족되어야 하는 레벨이 K 보다 크면 mid가 작아져야 함
            end = mid - 1
        elif sum <= K:
            start = mid + 1
            answer = mid
    
    return answer

print(bsearch(level))