매개변수 탐색 · 알고리즘 노트

개념

최적값을 직접 찾는 대신, 특정 값이 가능한지 판정하는 문제로 바꾸어 이분 탐색합니다. 판정 결과가 한 경계를 기준으로 바뀌는 단조성이 필요합니다.

가능한 최대 길이

여러 막대를 같은 정수 길이로 잘라 적어도 $K$ 개를 만들려고 합니다. 길이 $x$ 로 만들 수 있는 조각 수는 각 막대 길이를 $x$ 로 나눈 몫의 합입니다. $x$ 가 커질수록 조각 수는 늘어나지 않습니다.

어떤 길이가 가능하면 그보다 짧은 길이도 가능합니다. 가능한 길이를 만나면 정답 후보를 기록하고 더 긴 쪽을 탐색합니다. 불가능하면 더 짧은 쪽을 탐색합니다.

길이 $4,7$ 인 막대에서 $3$ 개를 만들 때 길이 $3$ 은 가능하고 길이 $4$ 는 불가능하므로 최대 길이는 $3$ 입니다.

자르는 길이	길이 $4$ 에서 얻는 개수	길이 $7$ 에서 얻는 개수	합계	$3$ 개 이상 가능 여부
$1$	$4$	$7$	$11$	가능
$2$	$2$	$3$	$5$	가능
$3$	$1$	$2$	$3$	가능
$4$	$1$	$1$	$2$	불가능
$5$	$0$	$1$	$1$	불가능

길이 $4$ 가 불가능하다면 더 긴 길이는 개수가 더 줄거나 같으므로 모두 불가능합니다. 길이 $2$ 가 가능하다면 더 짧은 길이도 모두 가능합니다. 이 성질을 이용해 가능·불가능이 바뀌는 경계를 찾습니다. 판정 결과가 가능, 불가능, 가능처럼 다시 바뀌는 조건에서는 이 방식으로 범위를 제외할 근거가 없습니다.

복잡도

막대 수를 $N$ , 가장 긴 막대의 길이를 $L$ 이라고 합니다.

연산	시간복잡도	공간복잡도
정한 길이로 자를 수 있는지 확인	$O(N)$	추가 $O(1)$
가능한 최대 길이 탐색	$O(N\log L)$	입력 저장 $O(N)$

예제

문제

막대를 같은 정수 길이로 잘라 적어도 $K$ 개의 조각을 만든다. 가능한 가장 긴 조각의 길이를 구하여라. 자르고 남은 부분은 사용하지 않는다.

입력

첫째 줄에 막대 수 $N$ 과 목표 조각 수 $K$ 가 공백을 사이에 두고 주어진다. $1\le N\le100$ ; $1\le K\le10\,000$ 이다.

둘째 줄에 각 막대의 길이 $a_1,a_2,\ldots,a_N$ 이 공백을 사이에 두고 주어진다. $1\le a_i<10\,000$ 이다.

출력

가능한 최대 길이를 출력한다. 길이 $1$ 인 조각도 충분히 만들 수 없으면 $0$ 을 출력한다.

예제 코드

C++20

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> v;

int main() {
    int n, k, i, l, r, m, cnt, ans;

    cin >> n >> k;
    v.resize(n);
    for (i = 0; i < n; ++i) {
        cin >> v[i];
    }
    l = 1;
    r = *max_element(v.begin(), v.end());
    ans = 0;
    while (l <= r) {
        m = (l + r) / 2;
        cnt = 0;
        for (int x : v) {
            cnt += x / m;
        }
        // 필요한 조각 수를 만들 수 있으면 답을 저장하고 더 긴 길이 탐색
        if (cnt >= k) {
            ans = m;
            l = m + 1;
        }
        // 조각 수가 부족하면 길이를 줄여 다시 탐색
        else r = m - 1;
    }
    cout << ans << '\n';
}

Java 17

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in;
        int n, k, i, l, r, m, cnt, ans;
        int[] a;

        in = new Scanner(System.in);
        n = in.nextInt();
        k = in.nextInt();
        a = new int[n];
        r = 0;
        for (i = 0; i < n; ++i) {
            a[i] = in.nextInt();
            r = Math.max(r, a[i]);
        }
        l = 1;
        ans = 0;
        while (l <= r) {
            m = (l + r) / 2;
            cnt = 0;
            for (int x : a) {
                cnt += x / m;
            }
            // 필요한 조각 수를 만들 수 있으면 답을 저장하고 더 긴 길이 탐색
            if (cnt >= k) {
                ans = m;
                l = m + 1;
            }
            // 조각 수가 부족하면 길이를 줄여 다시 탐색
            else r = m - 1;
        }
        System.out.println(ans);
    }
}

Python 3

n, k = map(int, input().split())
lst = list(map(int, input().split()))
l, r = 1, max(lst)
ans = 0

while l <= r:
    m = (l + r) // 2
    cnt = sum(x // m for x in lst)
    # 필요한 조각 수를 만들 수 있으면 답을 저장하고 더 긴 길이 탐색
    if cnt >= k:
        ans = m
        l = m + 1
    else:
        # 조각 수가 부족하면 길이를 줄여 다시 탐색
        r = m - 1

print(ans)

2.11.2 Parametric Search

개념

가능한 최대 길이

복잡도

예제

문제

입력

출력

예제 입력

예제 출력

예제 코드