파라메트릭 서치

이분 탐색 -> 값을 탐색하는 문제

파라메트릭 서치 -> 어떤 파라미터로 가능하냐? 라는 결정 문제

 

어떤 값을 만족하는 것을 찾는 탐색 문제가 아님. 먼저 답을 정해놓고, 그게 실제로 가능하냐를 찾는 문제임

 

어떤 연속된 입력들에 대해 그룹으로 쪼개고, 거기서 가능한 어떤 값을 찾는 그런 문제를 만났다고 쳐보자

 

e. g) 전체 수 N, 분할 가능 수 M , 배열 A[1:N] 에서 그룹으로 분할했을 때, 각 그룹 내의 원소 합의 최소값 구하기

 

여기서 쪼개는 방법부터 생각하면 머리가 쪼개진다

 

임의의 어떤 답의 후보를 정해두고, 이걸 만족하는지 값을 이분 탐색으로 변경해가며 확인하면 됨

근데 그룹을 쪼개는 방법을 모르는데 어케 확인함?

 

일단 "연속된 것"을 나눈다는 것에 집중해야 함

어차피 연속되어 있고, 우리는 조건을 만족하는 그룹인지 아닌지만 궁금한 거니깐

1~N 만큼 조회하면서 특정 조건을 만족하면 그룹 수 ++, 조건 관련 초기화(sum=0 등) 해주면 됨

 

쪼개는 방법 같은거 아무도 안궁금해 하니깐, 이 문제를 결정 문제로 바꿔서 푸는 게 중요함

 

문제 예시

https://www.acmicpc.net/problem/17951

 

코드

#include<iostream>
using namespace std;
int items[100005];
int main() {	
	cin.tie(0);
	cin.sync_with_stdio(false);

	int N, M;
	int sum = 0;
	cin >> N >> M;
	
	for (int i = 0; i < N; i++) {
		cin >> items[i];
		sum += items[i];
	}
	int lowValue = 0;
	int highValue = sum;
	int ans = 0;

	while (lowValue <= highValue) {
		// 일단 순회
		int targetValue = (lowValue + highValue) / 2;
		int overGroup = 0;
		sum = 0;
		for (int i = 0; i < N; i++) {
			sum += items[i];
			if (sum >= targetValue) {
				// 목표치를 넘기는 그룹을 찾았음
				// sum 초기화 -> 새로운 그룹이라는 뜻
				overGroup++;
				sum = 0;
			}
			if (overGroup >= M) {
				// 목표치를 넘기는 그룹이 k 보다 많이 생성됨
				// 일단 이 값으로의 분할은 무조건 가능함
				// 따라서 정답 갱신 및 목표치의 오른쪽으로 이동
				ans = (ans < targetValue) ? targetValue : ans;
				lowValue = targetValue + 1;
				break;
			}
		}
		if (overGroup < M) {
			// 앞서 for문에서 못찾았다고 가정
			highValue = targetValue - 1;
		}
	}

	cout << ans << endl;

	return 0;
}

 

기타

 

지난번에 코테 봤는데 이게 문자열 등장 횟수로 변경되서 나왔음

물론 나는 못풀었다 ㅠ