백준 16564번: 히오스 프로게이머 (Python/Java)

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

16564번: 히오스 프로게이머

 

 

 

접근

---

이분 탐색 문제를 풀 때 제일 먼저 찾아야 하는 조건은 최솟값과 최댓값이다. 이분 탐색은 특정 정렬 혹은 범위를 반씩 나눠가며 탐색하는 알고리즘이다. 때문에 범위를 특정할 수 있는 최솟값과 최댓값을 구하는 것이 필수적이다.

 

예시를 통해 살펴보자. 여기서 구할 수 있는 최솟값은 당연하게도 가장 낮은 레벨인 10이다. 그럼 가장 높은 값은 무엇일까? 올릴 수 있는 레벨 10을 가장 높은 레벨의 캐릭터에 더한 값 30이다. 이제 문제 조건에 따르면 여기서 뭘 어떻게 하더라도 이 이하로 내려갈 수 없고, 이 이상으로 높아질 수 없다.

 

중간값을 구해보자(20) 이제 가장 낮은 레벨부터 차례대로 중간값을 만들기 위한 레벨이 몇인지 구한다. 만약 중간값을 만들기 위한 레벨의 합이 분배할 수 있는 레벨보다 크다면 답이 될 수 없다. 분배할 수 있는 레벨 내에서 만들 수 없는 값이기 때문이다. 이때는 최댓값을 중간값에서 1을 뺀 값으로 수정해준다.

 

만약 중간값을 만들기 위한 레벨의 합이 분배할 수 있는 레벨의 값보다 작다면 이 값은 만들 수 있는 값이다. 하지만 이보다 더 큰 값이 답이 될 수도 있다. 이때는 최솟값을 중간값에 1을 더한 값으로 수정해준다. 이와 같은 방법을 통해 계속 반복하다 보면 팀의 목표 레벨을 구할 수 있다. 그건 그렇고 MS 액티비전 블리자드 인수라니, 히오스에 마스터 치프 나오나요? 제발...

 

 

 

 

 

풀이

---

Python

memberNum, levelNum = map(int, (input()).split())

levelList = []
for i in range(memberNum):
    levelList.append(int(input()))

levelList = sorted(levelList)

start, mid, last = levelList[0], 0, (levelList[(memberNum-1)]+levelNum)
result = 0
while start <= last:
    
    levelSum = 0
    mid = (start+last)//2

    for i in range(memberNum):
        if levelList[i] >= mid:
            break

        levelSum += (mid - levelList[i])

    if levelSum <= levelNum:
        result = mid
        start = mid + 1
    else:
        last = mid - 1

print(result)

 

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        
        Scanner scan = new Scanner(System.in);

        String[] firstLine = (scan.nextLine()).split(" ");
        int memberNum = Integer.parseInt(firstLine[0]);
        int levelNum = Integer.parseInt(firstLine[1]);

        int[] levelList = new int[memberNum];
        for(int i = 0 ; i < memberNum ; i++){
            levelList[i] = Integer.parseInt(scan.nextLine());
        }

        Arrays.sort(levelList);

        int start = levelList[0], mid = 0, last = (levelList[(memberNum-1)] + levelNum);
        int result = 0;
        while(start <= last){

            long levelSum = 0;
            mid = (start+last)/2;

            for(int i = 0 ; i < memberNum ; i++){
                if(levelList[i] >= mid){
                    break;
                }

                levelSum += (mid - levelList[i]);
            }

            if(levelSum <= levelNum){
                result = mid;
                start = mid + 1;
            }else{
                last = mid - 1;
            }

        }

        System.out.println(result);

    }

}

 

 

 

후기

---

정말 오랜만에 풀어본 이분 탐색 문제. 분명 이분 탐색을 전에도 몇 문제 풀어봤는데, 이번 문제는 너무 오랜만에 풀어보는 이분 탐색 문제다 보니 초반에 조금 헷갈려했다. 그동안 한두 달 정도는 너비 우선 탐색, 또 지난 2,3주간은 그리디 문제만 풀며 알고리즘을 다양하게 풀지 않아 생긴 문제라고 생각한다. 편식하지 말고 고루고루 풀어봐야겠다.