Parametric Search (매개변수 탐색)

[코드 출처 : 삼성 SW Expert Acadamy]

/*
Parametric Search란,
정답 후보 값을 이분 탐색하면서, 각 후보가 조건을 만족하는지 판정하는 방식으로 최적의 값을 찾는 알고리즘 기법이다.

[문제]
길이가 각각 다른 K개의 리본을 가지고 있다.
공예작품을 만들기 위해 가지고 있는 리본을 잘라서 길이가 동일한 N개의 리본재료를 만들려고 한다.
리본재료의 최대 길이를 구하시오. ( 1 <= K <= 10,000; 1 <= N <= 1,000,000; K <= N )
- 손실되는 길이는 없음
- 만들 수 없는 경우는 없다
- 이미 자른 리본은 붙일 수 없다
- 자를 때는 정수 cm 단위로 자른다

[접근법]
답을 찍어본다. -> 그 답이 되냐 안 되냐를 확인한다. -> 되면 줄이고, 안 되면 늘린다.
*/

#include <iostream>

using namespace std;

#define MAX_RIBBON 100

int K, N;       // K : 리본의 개수, N : 필요한 리본재료의 개수
int lowV, highV, midV;  // lowV : 리본재료 길이의 최솟값, highV : 리본재료 길이의 최댓값, midV : 리본재료 길이의 중간값
int numRibbonTape, bestV;   // numRibbonTape : midV 길이로 잘랐을 때 얻어지는 리본재료의 개수, bestV : 리본재료 길이의 최적값
int sizeRibbonTape[MAX_RIBBON];   // sizeRibbonTape[] : 리본의 길이 배열

void search() {
    midV = lowV + (highV - lowV) / 2;   // 중간값 계산
    numRibbonTape = 0;

    for (int i = 0; i < K; i++) {   // 리본 자르기
        numRibbonTape += sizeRibbonTape[i] / midV;
    }

    if (numRibbonTape >= N) {   // 리본재료를 N개 이상 만들 수 있는 경우
        if (bestV < midV) {
            bestV = midV;   // 최적값 갱신
            lowV = midV + 1;    // 길이를 늘려본다
        } else {    // N개를 만들지 못한 경우 -> 길이를 줄여야 한다
            highV = midV - 1;
        }
    }
}

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

    int T;
    cin >> T;

    for (int test_case = 1; test_case <= T; test_case++) {
        lowV = 1;
        highV = 0;
        bestV = -1;

        cin >> K >> N;

        for (int i = 0; i < K; i++) {
            cin >> sizeRibbonTape[i];
            if (highV < sizeRibbonTape[i]) {
                highV = sizeRibbonTape[i];   // 리본재료 길이의 최댓값 갱신
            }
        }

        while (lowV <= highV) {
            search();
        }

        cout << "#" << test_case << " " << bestV << "\n";
    }

    return 0;
}

문제 상황

• 리본 테이프 K개를 잘라서 길이 L짜리 조각을 N개 이상 만들 수 있는가?

정답은 무엇인가?

• 모든 리본을 길이 L로 잘랐을 때, 조각을 N개 이상 만들 수 있는 가장 큰 L. 즉, L이 정답이다.

왜 단순 탐색이 아니라 이분탐색(Parametric)인가?

• 단조성(monotonicity) 을 띄기 때문이다.

  L이 커질수록

  • 한 조각이 길어지니까.
  • 만들 수 있는 조각 개수 numRibbonTape는 같거나 줄어든다.
  • 즉, L이 작으면 : N개 이상 만들기 쉬움(가능)
  • L이 크면 : N개 이상 만들기 어려움(불가능)

  L : 1 2 3 4 5 6 7 ...
       T T T T F F F ...

  위 예시처럼 T/F가 한 번만 바뀌며, 연속적이라서 경계(최대 True)를 이분탐색으로 찾을 수 있다.

이 코드에서 판정 함수는 무엇인가?

• search() 함수에서 사실상 check(mid) + 이분탐색 범위 갱신을 같이 하고 있다.

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

• 위 코드의 의미는
  • i번째 리본 길이가 sizeRibbonTape[i]
  • 이를 길이 mid로 자르면 조각 수는 sizeRibbonTape[i] / mid
  • 전부 합치면 mid길이 조각을 총 몇 개 만들 수 있는지 numRibbonTape
• 따라서 판정은

if (numRibbonTape >= N)		// mid 길이로 N개 이상 가능한가?

이 식이 바로 check(mid)인 것.

Parametric Search의 흐름을 코드로 매핑한다면?

1. 탐색 구간 설정

low = 1;	// 길이가 0이 될 수는 없으므로 lower bound는 1
high = max(sizeRibbonTape[i];		// 가장 긴 리본보다 더 길게 자르는 건 불가능하니 upper bound

• 즉, 정답 L은 반드시 [1, maxRibbon] 안에 있다.

2. 중간값 mid를 찍어보고 판정
   `mid = low + (high - low) / 2; // Overflow 방지 형태의 계산

3. 판정 결과로 구간 세밀화

• numRibbonTape >= N인 경우
  • mid 길이로 N개 이상 만들 수 있다는 뜻.
  • 우리는 "최대 L"을 찾고 있으니 더 큰 길이를 시도 -> low = mid + 1
  • 동시에 현재 가능한 답 후보를 저장 -> max = mid 갱신.
• numRibbonTape < N인 경우
  • mid 길이로 N개를 만들지 못한다는 뜻.
  • 길이를 줄여야 답을 만족하므로 high = mid - 1

왜 max를 따로 저장하나?

• 이분탐색이 끝나면 low/high가 교차하면서 종료하는데, 종료 순간의 mid는 마지막으로 찍은 값을 뿐, 정답은 아닐 수도 있기 때문이다. 그래서 가능한 순간마다 max값을 갱신하며 '가능했던 길이 중 최대'를 기록해둔다.

즉, Parametric Search를 사용한 근거는

1. 정답 L을 직접 만들어내는 게 아니라
2. 어떤 L이 가능한지 check(L)로 판단하고
3. 가능/불가능이 단조성을 가진다는 점을 이용해
4. 이분탐색으로 최대한 가능한 L을 찾는다.

시간 복잡도

• check(mid) 계산 : K개 리본을 한 번 훑음 -> O(K)
• 이분탐색 반복 횟수 : 대략 log2(high)
• 총 O(K log maxRibbon)