BOJ - 2792, 보석 상자 매개 변수 탐색 (이분 탐색)

이번 문제는 매개 변수 탐색(parametric search) 문제입니다.

2792번: 보석 상자

그동안 그냥 이분 탐색이겠거니 하고 풀이했는데, 매개 변수 탐색 문제는 이분 탐색 기법을 적용하지만 다음과 같이 약간의 개념 차이가 있었습니다.

 

매개 변수 탐색이란?

이진 탐색(이분 탐색)을 사용해서 조건에 만족하는 최댓값을 구하는 방법을 의미한다.

 

정리하면, 기존의 이분(이진) 탐색은 수열 내에서 lower-bound 또는 upper-bound로 대소 비교를 통해 찾고자 하는 수의 위치를 탐색하는 방식이었다면

 

그 탐색의 조건을 특정 조건의 만족 여부로 따지는 것이 매개 변수 탐색이라고 정리할 수 있을 것 같습니다.

---

문제

수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.

즉, Ai + ... + Aj (i ≤ j)의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)

둘째 줄에 N개의 수 A1, A2,..., AN이 주어진다. (0 ≤ Ai ≤ 109)

출력

첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.

예제 입력

5 3
1 2 3 1 2

예제 출력

7

---

풀이 과정 정리

매개 변수 탐색 방식을 채택했기 때문에 우선 어떤 조건에 따라 이분 탐색의 범위를 재조정할 것인지를 정해야 합니다.

이렇게 x(최대 보석의 수)를 매개 변수로 받아 분배 가능의 여부를 판단하는 함수를 구현했습니다.

저의 경우 한 사람에게 부여할 최대 보석의 수라는 기준으로 탐색의 범위를 좁히고, 최대 보석의 수를 정했을 때 n명의 아이들에게 배분이 가능한지 여부를 매개 변수 탐색의 조건으로 선택했습니다.

 

여기에 이분 탐색은 조건을 만족하는 값과 같거나 처음으로 큰 값을 찾아야 하기 때문에 lower-bound 방식의 이분 탐색을 구현했습니다. 

 

lower-bound와 upper-bound의 차이점은 아래의 문제 풀이 글에 더 자세히 정리해 두었습니다.

BOJ - 1300번, K번째 수 이분 탐색을 이용한 풀이 (C++)

저는 이렇게 정리했습니다.

---

제출한 소스 코드 (C++)

#include <iostream>
#define endl '\n'
#define MAX 300001

using namespace std;

int n, m; // n: 아이들의 수, m: 보석의 색상 종류
int jewelryBox[MAX]; // 보석 상자, 총 300001 가지 색상이 존재할 수 있다.

//x: 한 명이 최대로 가질 수 있는 보석의 수
bool checkIsPossible(int x) {
	long long childrenCnt = 0; //보석을 받은 아이들의 수를 센다.

	// 첫 번째 보석부터 마지막 보석까지 탐색한다.
	for (int i = 0; i < m; i++) {
		// 최대 x개씩 분배할 때, 몇 명의 아이들이 필요한지 계산
		childrenCnt += (jewelryBox[i] / x);
		if (jewelryBox[i] % x) {
			childrenCnt++;
		}
	}

	//n명의 학생에게 분배가 가능하면 true, 아니면(넘어서면) false를 반환한다.
	if (n < childrenCnt)
		return false;
	else
		return true;
}

int binarySearch() {
	// 2 * n까지도 int type에 담을 수 있다.
	int lo = 1, hi = 1000000001;

	while (lo < hi) {
		int mid = (lo + hi) / 2;

		// 성공했을 때에는 mid를 포함해서 범위를 재지정
		if (checkIsPossible(mid)) {
			hi = mid;
		}
		// 실패했을 때에는 mid를 제외하고 범위를 재지정
		else {
			lo = mid + 1;
		}
	}

	return lo;
}

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

	// 입력 부분
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		cin >> jewelryBox[i];
	}

	// logic 담당 + 출력
	if (n == 1) {
		cout << jewelryBox[0];
	}
	else {
		cout << binarySearch();
	}

	return 0;
}

/*
한 명에게 줄 수 있는 최대 보석의 수를 기준으로 이분 탐색

성공: 보석의 수를 줄인다.
실패: 보석의 수를 늘린다.

가장 처음 성공하는 경우를 찾아야 하니깐
포함하고 이상인 첫 번째 수를 찾는 lower-bound로 가야한다.
*/