백준 1654번 - 랜선 자르기

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

---

문제 분석

1. 이미 가지고 있는 랜선의 개수 K

2. 필요한 랜선의 개수 N

3. 출력 : N으로 만들 수 있는 최대 길이

 

---

풀이

1. 랜선 K 개 입력받을 배열 arr 생성

2. arr 오름차순 정렬(가장 큰 값이 마지막 인덱스로 가게 하기 위함)

3. 변수 네개 사용

  max : 자를 랜선의 최대 길이 담음 (최초엔 arr의 마지막 인덱스로 선언)

  min : 자를 랜선의 최소 길이

  mid : 랜선의 중간 길이

  cnt : 현재 자른 랜선 개수

4. 3의 변수들을 이용해 반복문 내에서 이분탐색 진행

• mid 에 중간값을 갱신해가며 arr의 값들 자르기
•  cnt에는 자른 랜선 개수를 누적하여 n과 비교

 

---

코드

public class Example1654 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int k = Integer.parseInt(str[0]);
        int n =Integer.parseInt(str[1]);

        long[] arr = new long[(int)k];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Long.parseLong(br.readLine());
        }
        Arrays.sort(arr);
        long max = arr[arr.length -1];
        long min = 1;
        long mid = 0;
        
        long cnt = 0;
        while(min <= max) {
            cnt = 0;
            mid = (max+min)/ 2;
            for (int i = 0; i < arr.length; i++) {
                cnt+= arr[i]/mid;
            }
            if (cnt >= n) {
                min = mid + 1;
            } else {
                max = mid - 1;
            }
        }
        System.out.println(max);
    }
}

 

---

댓글 피드백은 언제나 환영합니다!