백준 알고리즘 1654번: 랜선 자르기

문제 정보

---

1654번: 랜선 자르기

 

핵심

---

이분 탐색을 떠올려야 한다

 

내가 찾고자 하는 것은 N개의 랜선을 만들 수 있는 랜선의 최대 길이 이다

모든 길이를 탐색하여 랜선을 잘라보고, 최대 경우를 구하는 것은 불가능하므로 자연스럽게 이분 탐색을 시도해야 한다

우리가 흔히 사용했던 이분 탐색은 인덱스로 특정 수를 찾는 탐색을 많이 사용했다. 그래서인지 새로운 관점을 적용하기가 조금 어려웠던 문제라고 생각한다

 

풀이에서 min, max, mid 라는 변수가 등장한다

• min, max : 내가 구하고자 하는 수가 존재하는 범위를 뜻함
• mid : min과 max를 2분할 한 지점(실제로 자를 랜선의 길이를 뜻함)

 

예시를 들어보자

4 11
802
743
457
539

여기서 우리가 선택할 수 있는 랜선의 길이는 0~802(최댓값) 이다.

• min : 0
• max : 802
• mid : 401

 

mid로 잘랐더니 각 랜선들은 다음과 같은 개수로 잘려진다 (남은 부분은 버려지기에)

2
1
1
1

우리가 만들고자 하는 랜선의 개수(N) 인 11에 모자란 5가 나왔다

이 경우, 우리는 랜선의 길이를 더 짧게 만들어서 더 많은 랜선이 나오도록 해야 한다.

 

이분 탐색에서는 다음과 같은 로직으로 다음 범위를 지정한다

if (랜선의 개수가 부족한 경우)
	max = mid;
if (랜선의 길이가 더 많거나 같은 경우)
	min = mid + 1;

이렇게 하면, 개수가 부족하면 max를 내려서 mid값이 감소하여 나눠지는 랜선의 개수가 증가할 것이고

개수가 많다면 min을 올려서 mid값을 증가시켜 나눠지는 랜선의 개수를 증가시킬 것이다

 

여기서 같은 경우에도 min 을 mid+1 로 지정해주는 이유는 upper bound 이기 때문이다

간단하게 설명하면, 우리가 구해야 하는 것은 N개를 만들 수 있는 랜선의 최대 길이 이다

N개를 만들 수 있는 랜선의 길이는 많을 것이다.

• 만약 길이가 200일 때도 N개의 랜선이 나오고, 201일 때에도 N개의 랜선이 나온다면
• 당연히 201이 최대 길이이므로 이를 택해야 한다

 

따라서 우리는 upper bound 방식으로 구하다 보면, min >= max 가 될 때까지 반복될 것이고

해당 반복이 끝난 지점에서의 min - 1 값이 우리가 구하고자 했던 최대 길이가 될 것이다

 

 

풀이

---

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

public class Main {
    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[] cables = new int[K];
        long min = 0;
        long max = 0;
        for(int i=0; i<K; i++) {
            cables[i] = Integer.parseInt(br.readLine());
            max = Math.max(max, cables[i]);
        }
        max++;
        while(min < max) {
            long mid = (min+max) / 2;

            int divided = 0;
            for(int i=0; i<K; i++) {
                divided += (cables[i] / mid);
            }

            if(divided < N) {
                max = mid;
            } else {
                min = mid + 1;
            }
        }

        System.out.println(min-1);
    }
}

• max 값은 길이 중 최댓값 + 1이 되어야 하므로 max++ 을 시켜 준다
  • 길이 중 최댓값으로 나누는 경우가 최대 경우가 될 수 있기 때문이다

 

Reference

---

언급했던 upper bound 에 대해 잘 설명된 글이 있어 첨부한다

[백준] 10816번 : 숫자 카드 2 - JAVA [자바]

 

Source Code on GitHub

---