https://www.acmicpc.net/problem/16401
16401번: 과자 나눠주기
첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1,
www.acmicpc.net
풀이 방법
이분 탐색을 사용한다.
최악의 경우 조카에게 줄 수 있는 과자의 길이의 경우는 1 이상 10^9 이하가 되므로 완전 탐색하면 시간 초과가 일어난다. 따라서, 시간 복잡도가 O(log n) 로 검색 속도가 더 빠른 이분 탐색을 생각하였다.
먼저, 과자 배열을 오름차순 정렬해준다.
다음 이분 탐색에 필요한 left, right 기준은 조카에게 나누어 줄 과자의 길이로 설정한다.
left 는 최소 길이인 1, right는 배열의 마지막 과자 길이 즉, 입력 받은 과자의 최대 길이로 초기화한다.
그 다음 과자의 길이가 중간값 mid 일 때 나누어 줄 수 있는 조카의 수를 구하는 데 과자 배열을 반복문으로 탐색하면서 현재 과자의 길이가 mid 이상이면 과자의 길이를 mid 로 나눈 값을 조카의 수에 더한다.
앞서, 과자 배열을 오름차순 정렬하였기 때문에 뒤에서부터 탐색하여 mid 보다 짧아질 때 탈출해준다.
결과적으로 구한 조카의 수가 M 보다 작다면 과자의 길이가 너무 길다는 것이므로 right 를 mid -1 로 하여 과자 길이를 줄여주고, M 이상이면 left 를 mid + 1로 하여 과자 길이를 늘려준다.
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
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[] arr = new int[N];
String[] line = br.readLine().split(" ");
for(int i=0; i<N; i++) {
arr[i] = Integer.parseInt(line[i]);
}
Arrays.sort(arr); // 과자 길이 오름차순 정렬
int answer = 0;
int left = 1;
int right = arr[N-1];
while(left <= right) {
int mid = (left + right) / 2;
int cnt = 0;
for(int i=N-1; i>=0; i--) {
if(arr[i] < mid) {
break;
}
cnt += arr[i] / mid;
}
if(cnt >= M) { // M명 이상에게 나눌 수 있다면
answer = Math.max(answer, mid);
left = mid + 1;
} else { // M명에게 나누어 줄 수 없을 때
right = mid - 1;
}
}
System.out.println(answer);
}
}'알고리즘 > baekjoon' 카테고리의 다른 글
| 백준 13460 구슬 탈출2 자바(java) (0) | 2024.01.19 |
|---|---|
| 백준 1912 연속합 자바(java) (0) | 2024.01.19 |
| 백준 17143 낚시왕 자바(java) (0) | 2024.01.18 |
| 백준 3055 탈출 자바(java) (0) | 2024.01.17 |
| 백준 14499 주사위 굴리기 자바(java) (0) | 2024.01.16 |