코딩블로그
백준 1654번 - 랜선 자르기 JAVA 실버 2 본문
728x90
https://www.acmicpc.net/problem/1654
1654번: 랜선 자르기
첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그
www.acmicpc.net
처음에는 아..이분탐색으로 안풀어도 되네~이랬는데 역시
실패 코드(2%)
import java.util.*;
import java.lang.*;
import java.io.*;
// The main method must be in a class named "Main".
class Main {
public static int K,N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
K = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
long[] arr = new long[K];
for (int i = 0; i < K; i++) {
int temp = Integer.parseInt(br.readLine());
arr[i] = temp;
}
Arrays.sort(arr);
long limit = N / K;
long result = arr[0] / limit;
long ttt = 0;
while (ttt != N) {
ttt = 0;
if (result == 0) {
break;
}
for (long k : arr) {
long t = k / result;
ttt += t;
}
if (ttt == N) {
break;
}
if (result > 0) {
result--;
}
}
System.out.println(result);
}
}
정답
import java.util.*;
import java.lang.*;
import java.io.*;
// The main method must be in a class named "Main".
class Main {
public static int K,N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
K = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
long[] arr = new long[K];
for (int i = 0; i < K; i++) {
int temp = Integer.parseInt(br.readLine());
arr[i] = temp;
}
Arrays.sort(arr);
long max = arr[K-1];
max++;
long min = 0;
long mid = 0;
while (min < max) {
mid = (max + min) / 2;
long count = 0;
for (int i = 0; i < arr.length; i++) {
count += (arr[i] / mid);
}
if(count < N) {
max = mid;
}
else {
min = mid + 1;
}
}
System.out.println(min - 1);
}
}
UpperBound는 자연수범위에서 특정 길이보다 1이 크다는 의미이다.
이분탐색에서 UpperBound가 아주 유용하게 쓰이니 중요한 개념으로 숙지해야 겠다.
728x90