99클럽 코테 스터디 2일차 TIL + 이분탐색

[BOJ 1654: 랜선 자르기] 문제 바로가기

이미 몇 달 전 파이썬으로 풀어본 문제라 문제 설명은 생략!

그 때와 같이 while문을 활용해 이분탐색을 수행했다.

문제는 자료형을 long으로 맞춰줘야 주어진 랜선 길이까지 모두 계산이 가능하다.

이를 알지 못해 int로 계속 제출을 시도했고, 틀렸다는 결과를 받았다.

import java.io.*;
import java.util.*;

public class jan_14th {
    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());   // 필요한 랜선 개수
        
        int [] lengths = new int[K];

        for(int i = 0; i < K; i++){
            lengths[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(lengths);

        // int result = 0;
        long start = 1;
        long end = lengths[K-1];
        // long result = 0;

        while(start <= end){
            long lan_counts = 0;
            long mid = (start + end) / 2;
            for (int length: lengths){
                lan_counts += length / mid;
            }
            if(lan_counts >= N) {
                start = mid + 1;
            }
            else end = mid -1;
        }
        System.out.println(end);
    }
}

오늘 문제를 풀면서 생각보다 문제에서 주어지는 조건을 잘 봐야함을 알게 됐다.