[백준] 16401번 과자 나눠주기 (Java)

---

문제

 

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

 

---

풀이

알고리즘 설계[접근 방식] : 이분탐색

과자의 길이는 1,000,000,000 십억보다 작으므로, 줄 수 있는 과자의 길이는 0과 십억 사이에 있다.

그래서 최소 길이를 1로, 최대 길이는 가지고 있는 과자의 최대 길이 값으로 두고 이분 탐색으로 풀었다.

 

풀이 과정

1.

조카의 수와 과자의 수를 입력받기

 

2.

과자 길이 배열을 만들고, 각각의 과자 길이를 배열에 저장한다.

 

3.

과자의 길이를 정렬한다.

 

4.

최소 값은 1로, 최대 값은 가지고 있는 과자의 길이 최대 값으로 설정한다.

 

5.

이분탐색으로 최소 값과 최대 값의 중간 값의 길이로 조카들에게 과자를 나눠줄 수 있는지 확인한다.

 

6.

나눠줄 수 있으면, 최소 값을 중간 값+1로 변경한다.

 

7.

나눠줄 수 없으면 최대 값을 중간 값-1로 변경한다.

 

8.

최소 값이 최대 값보다 크게되면 반복문을 종료한다.

 

 

 

---

코드

 

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int answer = 0;
		
		//조카의 수
		int n = sc.nextInt();
		
		//과자의 수
		int m = sc.nextInt();
		
		//과자 길이 배열
		int[] arr = new int[m];
		for(int i=0; i<m; i++) {
			arr[i] = sc.nextInt();
		}
		
        //정렬
		Arrays.sort(arr);
		
		//이분 탐색 최소 최대값
		int min = 1;
		int max = arr[m-1];
		
		//이분 탐색
		while(min<=max) {
			
			//중간 값
			int mid = (min+max)/2;
			
			//현재 조카들에게 나눠줄 길이
			int length = mid;	
			
			//가능한지 확인
			int count = 0;
			for(int i=m-1; 0<=i; i--) {
				int cur =(int)Math.floor(arr[i]/length);
				count+=cur;
				
				if(cur==0) break;
				else if(n<=count) break;
			}
			
			//가능하다면,
			if(n<=count) {
				answer=length;
				min=mid+1;
			}
			
			//불가능 하다면
			else if(count<n) {
				max = mid-1;
			}
		}
		
		//출력
		System.out.println(answer);
	}
}