[BOJ6236] 용돈 관리 & [자료구조] 파라메트릭 서치

[BOJ6236] 용돈 관리 & 파라메트릭 서치

파라메트릭 서치란?

1. 이진탐색(Binary Search)

• 이진 탐색은 정렬된 일련의 값들이 주어졌을 때 그 값들 중에서 원하는 값을 찾는 알고리즘.
• 이진 탐색은 처음에 중간값을 선택하여 그 값과 찾으려는 값을 비교하여 클 경우 선택했던 중간값을 최소값으로, 작을 경우 중간값을 최대값으로 하여 원하는 값을 찾을 때까지 반복하는 알고리즘.
• 시간복잡도는 O(logN)

2. 파라메트릭 서치(Parametric Search)

• 이진 탐색과 매우 유사하고 동일한 원리를 가지지만, 활용의 차이가 다소 있다.
• 주어진 범위 내에서 원하는 값 또는 원하는 조건에 가장 일치하는 값을 찾아내는 알고리즘.
• 최적화 문제를 결정 문제로 바꾸어 풀 수 있게 되어 문제 접근이 상당히 용이해진다.
• 파라메트릭 서치의 쉬운 예시 문제 : 자동차를 탈 수 있는 사람 중 나이가 가장 어린 사람을 찾고자 한다. 이 때 자동차를 탈 수 있는 사람이라 함은 나이가 19세 이상이라고 가정한다.
• 위와 같은 예시를 통해 가장 어린 사람을 찾는 문제에서 이사람이 자동차를 탈 수 있는지의 결정문제로 바꾸어 해결하면 파라메트릭 서치를 정확히 사용했다고 할 수 있다.

문제 설명

• N일 동안 하루에 얼마를 쓸 수 있는지 사용할 금액이 정해지고, M번만큼 출금할 수 있다.
• 통장에서 출금한 돈으로 사용하다가 돈이 다 떨어지면 새로 같은 금액만큼 출금할 수 있다.
• 돈이 남아있더라도 그날 사용할 금액이 더 큰 경우 돈을 넣고, 새로 같은 금액만큼 출금할 수 있다.
• M번 출금횟수를 정확히 맞추기 위해 돈이 남더라도 다시 넣고 새로 출금할 수 있다.
• 이 때 최소 인출 금액 K를 출력하는 문제

코드 리뷰

• 파라메트릭 서치를 사용하여 통장에서 인출해야할 최소 금액을 구하는 문제에서 특정 금액을 인출했을 경우 예산대로 돈을 사용할 수 있는가에 대한 결정문제로 변환하여 푼다.
• 즉 N일 동안 사용금액중 최대 금액~ N일 동안의 사용금액 총합까지의 범위를 이진탐색을 이용하여 그 금액으로 M번만큼 출금하여 N일을 사용할 수 있는지를 확인한다.
• 가능하거나 불가능한 상황에 맞춰 금액의 범위를 줄여나간다. 그 후 그 범위 중 최소 값을 출력하면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int N, M;
vector <int> board;
int ans = 1000000000;

void bs(int left, int right) {
	if (left > right) return;
	int mid = (left + right) / 2;
	int cnt = 1, num = mid;
	for (int n = 0; n < N; n++) {
		if (board[n] > mid) break;
		else {
			if (board[n] <= num) {
				num -= board[n];
			}
			else {
				cnt++;
				num = mid;
				num -= board[n];
			}
		}
	}
	if (cnt <= M) {
		ans = min(ans, mid); //조건이 맞는 가능한 값들에 대해 가장 최적의 조건을 찾아가는 과정
		bs(left, mid - 1);
	}
	else { // 조건에 맞지 않는 범위들은 이진탐색방식으로 버려준다.
		bs(mid + 1, right);
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> M;
	int min_range = 0, max_range = 0;
	for (int n = 0; n < N; n++) {
		int num;
		cin >> num;
		board.push_back(num);
		max_range += num;
		if (min_range < num) min_range = num;
	}
	bs(min_range, max_range);
	cout << ans << "\n";
	return 0;
}