[Baekjoon] 1654 - 랜선 자르기

📝 문제

 

 

❗ 주의

· 랜선의 최대 길이가 2^31 - 1 이므로 딱 int형이다. 그러므로 랜선으로 연산하는 경우에는 변수들을 다 long으로 써주는 것이 좋다. (mid를 구하거나, 랜선 총 개수를 구할때 오버플로우 날 수 있음). 나는 입력 변수들만 int로 받고 그 외는 전부 long으로 선언했다.

 

· 처음에는 end를 가장 짧은 랜선의 길이로 잡아야 하는거 아닌가 생각했다. 그래야 어떤 랜선이든 최소 1개씩은 잘리니까. 그러나 문제를 읽어보면 무조건 모든 랜선이 잘려야 한다는 조건은 없다. (안 잘리는 랜선이 있어도 됨) 예를 들어 랜선이 2개이고 각 길이가 2, 100이며, 총 10개를 잘라야 한다면 그냥 10으로 10개를 자르는게 최선이다. (길이가 2인 랜선은 버린다). 근데 만약 end를 가장 짧은 랜선의 길이로 잡으면 답이 2가 나오겠쥬?

 

 

🔑 풀이 과정

이 문제가 이분 탐색을 사용해서 매개 변수 탐색을 하는 문제라는데,

매개 변수 탐색이라는 걸 이 문제로 처음 들어봤다 ㅎ..

 

간략하게 설명하자면 어떤 범위에서 조건을 만족하는 범위가 있을 때,

어떤 시점까지는 조건을 만족하다가 그 시점 이후로는 조건을 만족하지 않는 경우가 나올것이다. 그 시점을 찾는 것이다.

찾아보니까 가능한 경우의 최댓값 or 최솟값을 구할때 사용하는 듯 싶다.

 

일반적인 탐색은 답을 찾으면 바로 종료하지만, 매개 변수 탐색같은 경우는 답을 찾더라도 더 탐색할 범위가 없을 때 까지 탐색하는 듯 하다.

 

<풀이 알고리즘>

start = 1 (0으로는 못 나누니깐), end = max인 이분 탐색을 사용한다.

(start = 랜선을 무조건 자를 수 있는 경우, end = 랜선을 무조건 못자르는 경우? 라고 생각하면 된다.)

1) 만약 현재 mid값으로 잘린 랜선들의 개수가 N보다 많으면

→ 더 크게 잘라서 최대 랜선의 길이를 구한다.

→ 다음 탐색에서 답이 없을 수도 있으니까 현재 mid값을 답으로 저장해둔다.

2) 만약 현재 mid값으로 잘린 랜선들의 개수가 N보다 작으면

→ 더 작은 길이로 잘라서 랜선들의 개수를 늘려준다.

 

 

🔓 답안

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int K = Integer.parseInt(st.nextToken()); //가지고 있는 랜선의 개수
        int N = Integer.parseInt(st.nextToken()); //필요한 랜선의 개수

        int[] arr = new int[K];
        int max = 0; //최댓값 저장 변수
        //랜선 길이 입력받으면서 최댓값 구하기
        for(int i = 0; i < K; i++){
            arr[i] = Integer.parseInt(br.readLine());

            if(arr[i] > max)
                max = arr[i];
        }

        long start = 1;
        long end = max;
        long mid;
        long sum; //총 랜선이 몇개 잘리는지 계산
        long result = 0;
        while(start <= end){
            sum = 0;
            mid = (start + end) / 2;

            for(int a : arr){
                sum += a / mid;
            }

            if(sum >= N){  //현재 mid 길이만큼 잘라서 나온 랜선의 총 개수가 N보다 많으면, 최대 랜선의 길이를 구해야 하므로 랜선 길이를 더 늘려서 계산해준다.
                result = mid; //현재 mid값이 정답일 수도 있으므로 값을 저장해 둠. (향후 탐색에서 만족하는 길이가 안 나올수도 있음)
                start = mid + 1;
            } else if(sum < N){ //현재 mid 길이만큼 잘라서 나온 랜선의 총 개수가 N보다 작으면, 더 작은 길이로 잘라서 랜선 개수를 늘려줘야함.
                end = mid - 1;
            }
        }

        bw.write(result + "\n");
        bw.flush();
        bw.close();

    }

}

 

 

 

🖤 알고리즘 분류

- 이분 탐색

- 매개 변수 탐색