BOJ) 랜선 자르기

랜선 자르기

1654번: 랜선 자르기

풀이

 

문제를 접했을 때 이분 탐색이라는 느낌이 강하게 들었는데, N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다는 조건이 있어서 이분탐색으로 푸는 것이라고 확신을 느꼈다.

 

랜선의 길이가 2^31 -1인 것에 대수롭지않게, int의 최대값이겠거니 하고 int형으로 모든 코드를 짰다.

하지만, 틀렸다고 뜨길래 설마하면서 int형의 최대 값을 찍어봤더니 80정도 차이가 났다.. 2^31 -1은 int가 아닌 long형이 필요했던 거다.

 

그래서 입력받은 것을 저장하는 것부터 시작해서, 이분 탐색 메소드까지 long형으로 바꿔주니 맞았다.

 

이분 탐색의 기준은 길이로 설정하고, left에는 최소인 1, right에는 Lan선의 최대 길이로 설정해준다.

최대 값을 입력받으면서 구해주어도 되지만, 파라메터가 이미 3개기도하고 조금 귀찮아서 Arrays의 sort로 오름차순 정렬한 다음 마지막 index를 가져왔다.

 

mid값으로 lan선을 잘르면 몇 개의 랜선이 나오는지 구하고, N이상일 경우에 답을 최대값으로 갱신하며 구해주었다.

로직 자체는 어렵지 않은 문제였다.

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class LanCutting_1654 {
    public static void main(String[] args) throws IOException { // 랜선 길이의 최대 값을 잘못보고 int형으로 설정해서 틀렸었음.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int k = Integer.parseInt(st.nextToken());
        long[] lanArr = new long[k];

        int n = Integer.parseInt(st.nextToken());
        for(int i=0; i<k; i++) {
            lanArr[i] = Long.parseLong(br.readLine());
        }

        solution(k,n,lanArr);

        br.close();
    }

    private static void solution(int k, int n, long[] lanArr) {
        System.out.println(binarySearch(k,n,lanArr));
    }

    private static long binarySearch(int k, int n, long[] lanArr) {
        Arrays.sort(lanArr);
        long left = 1, right = lanArr[k-1];
        long answer =0;

        while(left<= right) {
            long mid = (left+right)/2;
            if(getCnt(lanArr,mid) >= n) {
                answer = Math.max(answer, mid);
                left = mid+1;
            } else {
                right = mid-1;
            }
        }

        return answer;
    }

    private static long getCnt(long[] lanArr, long mid) {
        long result =0;
        for(long lan : lanArr) {
            result += lan/mid;
        }
        return result;
    }
}