(JAVA) 백준 2792번 : 보석 상자 --- [이진탐색]

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

2792번: 보석 상자

 

 

이분탐색 문제이다.

 

도저히 고민하다가 못풀겠어서

 

풀이 방법을 살짝(많이) 보고 이해한 다음 해결했다..

 

 

이분탐색 어렵다.

 

계속 관련 유형 문제들을 풀어봐야겠다.

 

 

 

 

핵심은 문제에 있다.

 

 

  1.  모든 보석을 N명의 학생들에게 나눠줘야 한다. 모든 보석이다. 하나라도 남으면 안된다.

 

 

  2.  보석을 받지 못하는 학생이 있어도 된다. 즉, 모든 보석을 나눠줘야 하지만 한명당 꼭 하나 이상씩 나눠줄 필요는 없다.

    한명한테 올인해도 된다. (이러면 질투심이 치솟는다.)

 

 

  3.  학생은 항상 같은 색상의 보석만 가져간다. 종류별로 하나씩(ex. 다이아, 루비, 사파이어 등) 가져갈 수 없다.

    무조건 한 종류의 보석만 가능하다. 다이아만 챙겨가야한다.

 

 

  4.  질투심의 최솟값을 구하는 문제.  질투심이란, 모든 학생들 중 보석을 가장 많이 가져간 학생의 보석 갯수 이다. 

    그렇기 때문에, 최대한 큰 오차없이 나눠줘야 한다.

 

 

 

이분탐색(Binary Search)을 사용해보자.

 

 

이분탐색이란, 정렬된 배열에서 중간 값과 찾을 값을 비교해서 크면 위 배열, 작으면 아래 배열만 탐색해나가는 알고리즘이다.

 

그렇기 때문에, log(n) 의 시간복잡도를 가진다.

 

 

이 문제는 1초이기 때문에 단순 탐색으로는 시간초과가 발생할 것이다.

그래서 이분탐색을 사용한다.

 

 

 

 

 

 

 

자, 그럼 여기서는 어떻게 이진탐색을 적용시킬까?

 

 

정렬된 배열 : 질투심의 범위(최소 범위 : 1, 최대 범위 : 여러 종류의 보석들 중 가장 개수가 많은 보석의 총 개수)

 

찾을 값 : 해당 질투심(중간 값) 을 만족하기 위해 필요한 최소 인원 수

    -  최소 인원 수 를 구하는 방법 : (해당 질투심 / 각 종류 별 보석의 개수) + 1  

    *** +1 을 하는 이유는 나머지 보석들을 막내 한 명이 짬처리해줘야 하므로.

    *** 그래서 만약 해당 질투심 % 각 종류 별 보석의 개수 가 0 이 나올 경우(나누어떨어짐) +1을 하지 않는다.

 

 

 

 

그래서 각 보석 종류 별로 최소 인원 수를 다 더했을 때,

 

 

N 보다 같거나 작으면 이 값을 저장하고, 아래 배열을 탐색한다.

*** 질투심을 더 낮출 수 있을 지 도전!

*** 남은 학생들에게는 안줘도 되니까 질투심이 성립한다.

 

 

N 보다 크면 위 배열을 탐색한다.

*** 절대 해당 질투심을 만족할 수 없음.

*** 질투심을 높여보자.

 

 

 

 

이렇게 하면 문제 해결!

 

감사합니다.

 

 

소스코드

---

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.StringTokenizer;
	// 이진탐색(=이분 탐색)
	// 보석 상자
	public class p2792 {
	static int[] colors;
	static int max;
	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 m = Integer.parseInt(st.nextToken());
	colors = new int[m];
	// 이진탐색 시 필요한 high(최대 범위) 를 입력할 때 구한다.
	for(int i = 0; i < m; i++) {
	colors[i] = Integer.parseInt(br.readLine());
	if(max < colors[i]) {
	max = colors[i];
	}
	}
	// Arrays.sort(colors);
	int min = search(n, m);
	System.out.println(min);
	}
	// 이진탐색으로 질투심 크기 범위를 구하고, 최소 크기를 얻는다.
	static int search(int n, int m) {
	int min = Integer.MAX_VALUE;
	int low = 1; // 무조건 1명은 들어가야함(=모든 보석을 나눠줘야함)
	int high = max;
	while(low <= high) {
	int mid = (low + high) / 2;
	int sum = 0;
	for(int ele : colors) {
	// 해당 mid 질투심을 얻기 위한 최소 인원 구하기.
	// 질투심보다 보석 개수가 작으면 1명만 있어도 되니까 + 1.
	// 단, 질투심 개수와 같을 경우 1명 추가하지 않아도 됨.
	int people = ele % mid == 0 ? ele / mid : ele / mid + 1;
	sum += people;
	}
	if(n >= sum) { // 해당 인원 내에 질투심을 만들 수 있으면 가능
	min = Math.min(min, mid);
	high = mid - 1;
	}
	else {
	low = mid + 1;
	}
	}
	return min;
	}
	}

view raw p2792.java hosted with ❤ by GitHub