문제 풀이 날짜: 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 링크 첨부)
'Study > Problem Solving' 카테고리의 다른 글
[백준 / Java] 14499번: 주사위 굴리기 (골드4) (0) | 2023.09.11 |
---|---|
[백준 / Java] 2613번: 숫자구슬 (골드2) (0) | 2023.09.11 |
[백준 / Java] 15683번: 감시 (골드4) (0) | 2023.09.11 |
[백준 / Java] 13023번: ABCDE (골드5) (0) | 2023.08.31 |
[SWEA / Java] 1767번: 프로세서 연결하기 (0) | 2023.08.30 |