[백준] 1654번 - 랜선 자르기 [Java][C++]

문제 링크

---

1. 문제 풀이

주어진 $K$ 개의 랜선을 적절한 길이로 잘라서 같은 길이를 갖는 $N$ 개 이상의 랜선을 만들어야 하는 문제다. 자를 길이를 길이 $1$ 부터 쭉 브루트 포스로 접근하면 탐색 범위가 너무 넓어서 시간 초과가 발생하기 때문에 효율적인 접근이 필요한데 매개 변수 이분 탐색을 활용하면 해결할 수 있다.

$N$ 개 이상의 랜선을 만들 수 있는 길이는 최소 $1$ 부터 최대 $2^{31} - 1$ 사이에는 반드시 존재하므로 이 중간 값을 기준으로 랜선을 잘라서 개수가 $N$ 개 보다 적으면 오른쪽 구간을 중간 값으로 옮긴 후 다시 중간 값을 계산하고, 개수가 $N$ 개 보다 크거나 같으면 왼쪽 구간을 중간 값 $+1$ 로 옮긴 후 다시 중간 값을 계산하는 과정을 반복하면 된다.

이 과정으로 $N$ 개 초과를 만들 수 있는 최소 길이를 찾은 후 $-1$ 을 하면 $N$ 개 이상 만들 수 있는 최대 길이를 구할 수 있다. 이를 위해 Upper Bound 이분 탐색을 기본으로 매개 변수 탐색을 수행했다.

---

2. 코드

1. 이분 탐색 + 매개 변수 탐색 [Java]

int 형 최댓값이 $2^{31} - 1$ 인데 Lower Bound, Upper Bound 이분 탐색은 범위를 넘는 칸까지 반환할 수 있어야 적절한 위치를 구할 수 있어서 오른쪽 구간의 초기값을 $2^{31}$ 로 설정해야 한다. 이를 위해 long 으로 타입을 통일했다.

mid 가 자를 길이가 되며 각 랜선에 대해 몫을 구하면 잘린 후 랜선의 개수가 된다.

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

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[] arr = new int[K];
        for (int i = 0; i < K; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        System.out.println(upperBound(arr, N) - 1);
    }

    static long upperBound(int[] arr, int key) {
        long left = 1;
        long right = Integer.MAX_VALUE + 1L;  // 랜선의 길이가 최대 2^31-1까지라서 right의 상한을 2^31로 설정

        while (left < right) {
            long mid = (left + right) / 2;

            long cnt = 0;
            for (int n : arr) {
                cnt += n / mid;
            }

            if (cnt >= key) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return right;
    }
}

2. 이분 탐색 + 매개 변수 탐색 [C++]

int 형 최댓값이 $2^{31} - 1$ 인데 Lower Bound, Upper Bound 이분 탐색은 범위를 넘는 칸까지 반환할 수 있어야 적절한 위치를 구할 수 있어서 오른쪽 구간의 초기값을 $2^{31}$ 로 설정해야 한다. 이를 위해 long long 으로 타입을 통일했다.

mid 가 자를 길이가 되며 각 랜선에 대해 몫을 구하면 잘린 후 랜선의 개수가 된다.

#include <bits/stdc++.h>
using namespace std;

long long upper_bound_param(const vector<int>& v, int key) {
    long long left = 1;
    long long right = INT_MAX + 1LL;  // 랜선의 길이가 최대 2^31-1까지라서 right의 상한을 2^31로 설정

    while (left < right) {
        long long mid = (left + right) / 2;

        long long cnt = 0;
        for (int n : v) {
            cnt += n / mid;
        }

        if (cnt >= key) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return right;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int k, n;
    cin >> k >> n;

    vector<int> v(k);
    for (int& x : v) cin >> x;

    cout << upper_bound_param(v, n) - 1;
}

---

3. 풀이 정보

1. 이분 탐색 + 매개 변수 탐색 [Java]

언어	시간	메모리	코드 길이
Java 11	160 ms	17504 KB	1115 B

2. 이분 탐색 + 매개 변수 탐색 [C++]

언어	시간	메모리	코드 길이
C++ 17	4 ms	2180 KB	752 B

---