문제 풀이 날짜: 2023.09.05
포스트 작성일: 2023.09.11

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 16401번: 과자 나눠주기 (실버2)

 

키워드

이분 탐색, 매개변수 탐색

 

풀이 접근법

  • 이분탐색의 일종인 매개 변수 탐색(Parametric Search)을 이용하는 문제이다.
  • 조카의 수보다 과자의 수가 적다면 과자를 1 단위까지 쪼갤 수 있다.
    • 단, 과자를 합칠 수는 없으므로 항상 큰 것을 쪼개서 작게 만들어야 한다.
  • 나눠줄 수 있는 인원이 총 몇 명인지는 나눗셈의 으로 구한다.
  • 길이 몇 짜리를 나누어줄 지는 이분탐색으로 찾아나간다. 개수가 많이 나왔다면 나눠줄 길이를 늘리고, 개수가 너무 적게 나왔다면 나눠줄 길이를 줄인다.

 

코드

import java.io.*;
import java.util.*;

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[] snacks = new int[N];
		
		st = new StringTokenizer(br.readLine(), " ");
		for(int i = 0; i < N; i++) {
			snacks[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(snacks);
		
		int result = 0;
		int maxSize = snacks[N - 1];
		
		int count = 0;
		for(int s : snacks) {
			count += s / maxSize; //초기 길이로 몇 명에게 줄 수 있는지 센다.
		}
		
		if(count >= M) {
			System.out.print(maxSize);
			return;
		}
		
		int left = 1;
		int right = maxSize;
		while(left <= right) {
			int mid = (left + right) / 2;
			
			count = 0;
			for(int s : snacks) {
				count += s / mid; //현재 길이로 몇 명에게 줄 수 있는지 센다.
			}
			
			if(count >= M) {
				result = Math.max(mid, result);
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}
		
		System.out.print(result);
	}

}

 

참고한 링크

 

git 링크

(git 링크 첨부)

+ Recent posts