[백준/Java] 1654 랜선 자르기
조건
-
가지고 있는 랜선의 개수는 K이다.
-
필요로하는 랜선의 개수는 N이다.
-
랜선의 최대값이 int 형의 최대 값이기 때문에 long으로 탐색한다.
-
K개의 랜선의 길이를 받고 그 값에서 필요로 하는 N개를 충족하며 최대길이의 랜선을 출력하면된다.
예제 입력
해설
랜선의 최소 길이에서 부터 최대 길이 까지의 범위를 가진채 이분탐색을 통해 해당 값으로 / 를 해보고 개수에 충족이 된다면 해당 길이의 값을 저장한 후 L <= R 될때 까지 이분 탐색을 실행한다.
그리고 최종적으로 저장된 값이 개수를 충족하는 최대 길이의 랜선이니 저장값을 출력하면 정답이 나온다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int K,N;
static int[] A;
static FastReader scan = new FastReader();
static StringBuilder sb = new StringBuilder();
static void input() {
K = scan.nextInt(); // 가지고 있는 랜선의 개수를 받는다.
N = scan.nextInt(); // 필요로 하는 랜선의 개수를 받는다.
A = new int[K+ 1]; //index 시작을 1로 하기 위해 N+1을 해준다.
for(int i=1;i<=K;i++) { //K의 값들을 받아준다.
A[i] = scan.nextInt();
}
}
static boolean findAns(long len) {
long sum =0;
for(int i = 1;i<=K;i++) {
sum += A[i] / len; // 이분 탐색으로 정해진 값에서 가진 랜선의 길이들을 나 // 눠 필요로 하는 개수가 충족되는지를 확인한다.
}
return sum >= N;
}
static void find() {
long L = 1, R = Integer.MAX_VALUE,ans=0; // 이분 탐색 범위를 정해준다.
while(L<=R) {
long mid = (R + L) /2;
if(findAns(mid)) { // 개수를 충족한다면 해당 값은 ans에 저장후 다음 이분탐 // 색을 시작한다.
ans = mid;
L = mid +1;
}else {
R = mid - 1;
}
}
System.out.println(ans); // 저장되어 있는 mid값을 출력한다.
}
public static void main(String[] args) {
input();
find();
}
static class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws FileNotFoundException {
br = new BufferedReader(new FileReader(new File(s)));
}
String next() {
while(st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch(IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
Long nextLong() {
return Long.parseLong(next());
}
double nextDouble(){
return Double.parseDouble(next());
}
String nextLine() {
String str = "";
try {
str = br.readLine();
}catch(IOException e) {
e.printStackTrace();
}
return str;
}
}
}
Author And Source
이 문제에 관하여([백준/Java] 1654 랜선 자르기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@heetaeheo/백준Java-1654-랜선-자르기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)