[실버 2] [Java] 백준 1654번: 랜선 자르기

아이디어

이진 탐색을 쓰는 문제이다.

입력된 랜선 중 가장 긴 랜선에서 한 토막의 길이를 결정해서

다른 랜선들도 그 토막의 길이만큼 나눈 다음 그 모든 토막들의 개수를 합해서 N개 이상인지를 확인할 것이다.

이진 탐색으로 진행하면 다음과 같은 알고리즘을 따른다.

 

init: 

left = 1, right = 제일 긴 랜선의 길이

 

while(left <= right):

{

mid = (left + right) / 2

mid로 모든 랜선들을 나눈 몫의 합이 N 이상이면 -> mid를 정답에 저장, left = mid + 1

아니면 -> right = mid - 1

}

 

이 방법대로 예제 입력대로 코드를 실행하면 다음과 같이 진행된다

 

mid = 401 -> left = 1, right = 400
mid = 200, ans = mid -> left = 201, right = 400
mid = 300 -> left = 201, right = 299
mid = 250 -> left = 201, right = 249
mid = 225 -> left = 201, right = 224
mid = 212 -> left = 201, right = 211
mid = 206 -> left = 201, right = 205
mid = 203 -> left = 201, right = 202
mid = 201 -> left = 201, right = 200

 

이를 코드로 구현하면 다음과 같다.

import java.io.*;

public class N1654 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] input =  br.readLine().split(" ");
        int K  = Integer.parseInt(input[0]);
        int N  = Integer.parseInt(input[1]);
        long[] lan = new long[K];
        long max = 0;

        for (int i = 0; i < K; i++) {
            lan[i] = Long.parseLong(br.readLine());
            if (lan[i] > max) { max = lan[i];}
        }

        long left = 1, right = max, ans = 0;
        while (left <= right) {
            long mid = (left + right) / 2;
            long cnt = 0;
            for (long l : lan) {
                cnt += l / mid;
            }

            if (cnt >= N) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        bw.write(ans+"\n");

        bw.flush();
        bw.close();
        br.close();
    }
}

 

---

아직 초보라 많이 서툴고 틀린 부분이 있을 수 있습니다. 고수분들께서 조언해주실만한 사항이 있으면 감사히 받겠습니다.