[BOJ/Java] 백준 16401번 - 과자 나눠주기

백준 #16401 과자 나눠주기

16401번: 과자 나눠주기

 

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

public class Main {
	
    public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int M = Integer.parseInt(st.nextToken());  // 조카 수
		int N = Integer.parseInt(st.nextToken());  // 과자 수
		int[] stick = new int[N];  // N개의 과자 길이
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < stick.length; i++) {
			stick[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(stick);
		int start = 1;
		int end = stick[N-1];
		int maxLen = 0;
		
		while (true) {
			int cnt = 0;
			if (start > end) {
				break;
			}
			int mid = (start + end) / 2;
			
			for (int i = 0; i < stick.length; i++) {
				cnt += stick[i] / mid;
			}
			
			if (cnt >= M) {
				start = mid+1;
				maxLen = Math.max(maxLen, mid);
			} else {
				end = mid-1;
			}
		}
		System.out.println(maxLen);
		
		
	}
}

이분탐색 기법을 사용했다. 1과 막대의 최대 길이의 중간값을 시작으로 탐색해주는데, 이 중간값이 나눠주려는 동일한 길이의 막대 과자가 된다. 따라서 이 값으로 각 과자 길이들을 나눠줬을 때 나오는 몫이 해당 과자에서 나눠줄 수 있는 동일한 길이의 막대 과자 개수가 된다. 이 개수가 조카 수보다 클 경우, 막대 길이를 더 늘일 수 있는 것으로 시작값을 중간값 + 1로 바꿔주고, 조카 수보다 작을 경우 끝값을 중간값 - 1로 바꿔준다. 바뀐 시작값과 끝값으로 중간값을 새로 구하며 가장 긴 길이를 찾는다.

 

---

 

max 값을 찾기 위해 정렬을 해줬는데, max 값 하나 때문에 정렬하기엔 비용이 크니 아래 방법을 통해 찾는 것이 나을 것 같다.

Arrays.stream(stick).max().getAsInt();  // max 값