[백준] 1654번 : 랜선 자르기

문제

www.acmicpc.net/problem/1654

1654번: 랜선 자르기

문제해결방법

이 문제는 랜선의 길이를 기준으로 이분탐색으로 풀었다.

left를 자를 수 있는 가장 작은 길이, right를 K개의 랜선 중 최대 길이로 두고 mid(=(left+right)/2)의 길이로 잘라보면서

만약 N개보다 적다면 left를 mid+1로 해서 다시 탐색하고 N개보다 많거나 같으면 mid로 최대 길이를 갱신해준다.

코드

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main1654_랜선자르기 {
 
    public static void main(String[] args) throws Exception {
        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 left = 1, right = Integer.MIN_VALUE;
        int[] line = new int[K];
        for(int i=0; i<K; i++) {
            line[i] = Integer.parseInt(br.readLine());
            if(right<line[i]) right = line[i];
        }
        long answer = 1;
        while(left<=right) {
            long mid = (left+right)>>1;
            long count = 0;
            for(int i=0; i<K; i++) {
                count += line[i]/mid;
            }
            if(count<N) right = mid-1;
            else {
                if(answer<mid) answer = mid;
                left = mid+1;
            }
        }
        System.out.println(answer);
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.