[백준 스터디 1주차] 16564번 히오스 프로게이머 실버1 - 자바(JAVA) / 이분탐색

📑 문제

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를 출력한다.

 

 

 

 

 

 

 

✒️ 풀이

 전형적인 이분탐색 문제이다.

 공유기설치(https://eijun.tistory.com/275)와 나무자르기(https://eijun.tistory.com/276) 문제를 풀었다면 쉽게 풀 수 있을 것이라 생각한다.

 설명은 생략한다.

 

 

 

 

 

 

 

🙋‍♀️ 의견

 이번 스터디에서 이분탐색 문제만을 골라 풀었기 때문에 자연스레 이분탐색으로 풀었지만, 문제 유형을 파악 못했다면 접근하는데 난항을 겪었을 것 같다.

 이분탐색 문제라는 삘을 받도록 자주 들여다 봐야겠다.

 

 

 

 

 

 

 

💻 소스코드: 자바(Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main_백준_16564_히오스프로게이머_실버1 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());//캐릭터들 개수
		int K = Integer.parseInt(st.nextToken());//올릴 수 있는 레벨 총합
		int[] levels = new int[N];//캐릭터별 레벨
		for (int i = 0; i < N; i++) {
			levels[i] = Integer.parseInt(br.readLine());
		}//input
		Arrays.sort(levels);
		
		int result = 0;
		int left = levels[0];
		int right = levels[N-1];
		while(left<=right) {
			int mid = (left+right)/2;
			long sum = 0;
			for (int i = 0; i < N; i++) {
				if(levels[i]<mid) sum += (mid-levels[i]);
			}
			if(sum<=K) {
				result = mid;
				left = mid+1;
			}else {
				right = mid-1;
			}
		}
		System.out.println(result);
	}//end of main
}//end of class

 

 

 

 

 

 

 

 

💎 💎 💎

 

 

Ｐｏｓｔｅｄ Ｂｙ ＳＡＹ

𝘛𝘩𝘢𝘯𝘬𝘴 𝘧𝘰𝘳 𝘳𝘦𝘢𝘥𝘪𝘯𝘨