---문제---
---코드---
import java.util.Arrays;
import java.util.Scanner;
public class Bj1654 {
public static long max_result;
public static long[] lines;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int K = sc.nextInt();
long N = sc.nextInt();
lines = new long[K];
for(int i=0; i<K; ++i) {
lines[i] = sc.nextInt();
}
sc.close(); sc= null;
Arrays.sort(lines);
if(N==1) {
System.out.println(lines[K-1]);
return;
}
else if(K==1) {
System.out.println(lines[K-1]/N);
return;
}
else if(N==2) {
System.out.println((lines[K-1]/2 > lines[K-2])? lines[K-1]/2 : lines[K-2]);
return;
}
else {
long left = lines[K-1]/N ;
long right = lines[K-2]+1;
max_result = 0 ;
if(left>=right) {
System.out.println(left);
return;
}
while(left<=right) {
long half = (left+right)/(long)2;
if(half==0) half = 1;
long sum = 0 ;
for(int i=0; i<K; ++i) {
sum += lines[i]/half;
}
if(sum<N) {
right = --half;
}else {
if(half>max_result) {
max_result = half;
}
left = ++half;
}
}
}
System.out.println(max_result);
}
}
기본적인 방식은, 제일 큰 원소를 N으로 나눈 값 (가능한 최소 후보) 과 두번째로 제일 큰 원소 (가능한 최대 후보) 를 범위로 두고
이분탐색을 진행하는 것입니다.
그러나 이 범위 경계를 만드는 과정에서 제일 큰 원소를 N으로 나눈 값이 두번째로 큰 값보다 크다면 ( if(left>=right) )
이분탐색을 할 필요가 없으므로 바로 제일 큰 원소를 N으로 나눈 값을 출력하면 됩니다.
이분탐색은, 가능 범위가 없어질 때 까지, left 와 right의 중간값을 구해서 가능한 갯수를 구하는 식입니다.
이 문제에서 가장 주의할 점은 2가지가 있습니다. (이 때문에 런타임 에러가 날 수 있습니다.)
첫번째는, 정수형 타입의 문제입니다.
half 를 구하는 과정에서 left = 1,100,000,000 right = 2,100,000,000 인 경우
left + right = 3,200,000,000 가 되는데 이는 int형의 최댓값을 훌쩍 넘는 값이므로 overflow가 나서
half의 값이 이상하게 나타나질 수 있기 때문에, 가능한 타입은 long 타입으로 해야합니다.
두번째는, half가 0이 되는 경우 입니다.
left = 0 , right = 1 인 경우 half = 0이 되기 때문에
sum 을 구하는 경우에서 0으로 나누게 되므로, 런타임 에러가 납니다.
따라서 half가 0이면 1로 바꿔주는 작업을 해야합니다.
---출처---
https://www.acmicpc.net/problem/1654
'Algorithms > Baekjoon' 카테고리의 다른 글
[Java] 백준 알고리즘 7568 번 문제 : 덩치 (Brute Force) (0) | 2020.08.10 |
---|---|
[Java] 백준 알고리즘 15649, 15650 번 문제 : N과 M 시리즈 (완전탐색) (0) | 2020.02.18 |
[Java] 백준 알고리즘 10816 번 문제 : 숫자 카드 2 (배열) (0) | 2020.01.15 |
[Java] 백준 알고리즘 2512번 문제 (이분 탐색) (0) | 2020.01.14 |
[Java] 백준 알고리즘 9095번 문제 (Dynamic Programming) (0) | 2019.12.30 |