[백준] 1654번: 랜선 자르기
📝문제
입력에 대해 문제에 주어진 조건을 만족하는 값을 찾는 문제라서 이분탐색 알고리즘을 사용했다.
시작값의 최솟값은 1, 최댓값은 입력 받은 랜선 길이 중 가장 큰 값으로 설정했다.
📌코드
package Baekjoon;
import java.util.*;
import java.io.*;
public class BOJ1654 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int k = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
long[] lan = new long[k];
long max = 0;
long min = 1;
for(int i = 0; i < k; i++){
lan[i] = Integer.parseInt(br.readLine());
max = Math.max(lan[i], max);
}
//최소 길이와 최대 길이를 시작으로 이분탐색한다
int answer = 0;
while(min <= max){
long mid = (max + min) / 2;
int result = 0;
for(long i : lan) {
result += (i / mid);
}
if(result < n){
max = mid - 1;
} else {
min = mid + 1;
answer = Math.max(answer, (int)mid);
}
}
System.out.println(answer);
}
}
Author And Source
이 문제에 관하여([백준] 1654번: 랜선 자르기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@paulus0617/boj1654
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
package Baekjoon;
import java.util.*;
import java.io.*;
public class BOJ1654 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int k = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
long[] lan = new long[k];
long max = 0;
long min = 1;
for(int i = 0; i < k; i++){
lan[i] = Integer.parseInt(br.readLine());
max = Math.max(lan[i], max);
}
//최소 길이와 최대 길이를 시작으로 이분탐색한다
int answer = 0;
while(min <= max){
long mid = (max + min) / 2;
int result = 0;
for(long i : lan) {
result += (i / mid);
}
if(result < n){
max = mid - 1;
} else {
min = mid + 1;
answer = Math.max(answer, (int)mid);
}
}
System.out.println(answer);
}
}
Author And Source
이 문제에 관하여([백준] 1654번: 랜선 자르기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@paulus0617/boj1654저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)