[백준] 16564 - 히오스 프로게이머 💠 (Python) / 실버 1 / 이분 탐색

BAEKJOON Logo

 

 

 

 

Contents

 

---

1.  문제🔥

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

문제

요약하자면, 게임 캐릭터 개수 N과 올릴 수 있는 레벨 총합 K가 주어집니다. N명의 캐릭터에게 레벨 K를 골고루 올릴 때, 가능한 팀의 목표 레벨(팀에서 제일 낮은 캐릭터의 레벨)중 최대 값을 출력해야 합니다.

1) 예제 입출력❄️

예제 입출력

3명의 캐릭터가 각각 레벨이 10, 20, 15인 경우 입니다. 올릴 수 있는 레벨은 10입니다. 골고루 분배했을 때, 최소 레벨의 최댓값을 구해야 합니다. 첫 번째 캐릭터에게 +7, 세 번째 캐릭터에게 +3 하면 레벨은 각각 17, 20, 18이 되어 최소 레벨이 17이 되며, 이게 최소 레벨의 최댓값입니다.

2. 핵심 논리☢️

찾고자 하는 팀의 목표 레벨(trg_level)을 찾기 위해, 그 레벨이 되는데 필요한 레벨 포인트(need_level)를 이분 탐색하는 것이 핵심입니다.

3. 풀이 코드✅

1) 코드

import sys
input=sys.stdin.readline
N,K=map(int,input().split())
x=[int(input()) for _ in range(N)]

s,e=min(x),max(x)+K
while s <= e:
    trg_level=(s+e)//2
    need_level = sum([trg_level-lv for lv in x if trg_level-lv >= 0])
    
    if need_level <= K:
        result = trg_level
        s = trg_level + 1
    elif need_level > K:
        e = trg_level - 1

print(result)

캐릭터 수 N과 올릴 수 있는 레벨 K를 입력받고, x에 캐릭터별 레벨을 리스트로 저장합니다. 이분 탐색할 범위를 s(start)와 e(end)로 정의해주는데, 캐릭터 중 제일 낮은 레벨부터, 제일 높은 레벨 + K까지로 설정합니다. while 문을 돌며 이분 탐색을 하는데, 팀의 목표 레벨을 trg_level로 설정하고 그 레벨을 팀의 목표 레벨로 하는데 필요한 레벨을 need_level에 설정합니다. x에서 각 레벨 중 trg_level보다 낮은 레벨만 trg_level이 되는데 필요한 레벨 포인트를 모두 더해서 need_level을 계산합니다. need_level이 K 이하라면 필요한 레벨(need_level) 보다 올릴 수 있는 레벨(K)이 크거나 같은 경우로, 아직 여지가 있기 때문에 s = trg_level + 1을 해줍니다. 이때 result = trg_level로 갱신해주는데, 다음 need_level이 K보다 커지는 경우 현재 trg_level이 정답이기 때문입니다.

2) 주석 달린 코드

import sys
input=sys.stdin.readline
N,K=map(int,input().split()) # 캐릭터수 N과 올릴 수 있는 레벨 K
x=[int(input()) for _ in range(N)] # 캐릭터별 레벨 리스트

s,e=min(x),max(x)+K # 캐릭터중 제일 낮은 레벨 ~ 높은 레벨 + K 까지 이분탐색
while s <= e:
    trg_level=(s+e)//2 # 팀의 목표레벨
    need_level = sum([trg_level-lv for lv in x if trg_level-lv >= 0]) # 거기에 필요한 레벨
    
    if need_level <= K: # 필요한 레벨보다 올릴 수 있는 레벨(K)이 크거나 같은 경우
        result = trg_level # result를 갱신
        s = trg_level + 1
    elif need_level > K: # 필요한 레벨 보다 올릴 수 있는 레벨(K)이 작은 경우
        e = trg_level - 1

print(result)

 

 

읽어주셔서 감사합니다.

다음에 더욱 유익한 글로 찾아오겠습니다.

 

* 관련 풀이 코드는 아래 깃허브 링크에 있습니다.

https://github.com/netsus/BaekJoon/blob/master/jupyter/16564_%ED%9E%88%EC%98%A4%EC%8A%A4_%ED%94%84%EB%A1%9C%EA%B2%8C%EC%9D%B4%EB%A8%B8.ipynb

GitHub - netsus/BaekJoon: Algorithm Problem solving

Reference)
1. BAEKJOON Logo: https://www.acmicpc.net/