[백준 6236번 / C++] 용돈 관리

이분 탐색 문제이다. 

 

어떤식으로 이분 탐색을 활용하는지 한번 살펴보자. 

 

먼저 비교할 값을 이분탐색을 통해서 추출해낸다. 

예를 들어 low 값과 high 값을 1과 100000값으로 정했으면 low와 high를 이용해 중간값을 구할 수 있다. 

다음 그림을 한번 살펴보자. 

즉, 첫 중간값은 50,000이 되고 두번째 중간값은 25,000 ... 이런식으로 계속 분할하다 보면 

mid가 50일 때가 나올것이다. 이때를 한번 살펴보자 

 

밑에 그림에서 현우가 날마다 사용하려고 하는 돈이 

"10 40 30 10 50 10 40" 이라고 가정을 하자. 

 

현재 mid 값인 50으로 현우가 날마다 사용하려고 정한 돈을 계속해서 빼주고 충당이 안된다면 다시 mid값을 초기화 시켜서 반복한다. mid값을 다시 초기화 시키는 작업에서 카운팅을 해주는데 이 값으로 m값과 비교하면 된다. 

#include <iostream>
#include <vector>
using namespace std; 
int n, m;
vector <int> v; 
bool check(int mid) {	
	int temp = mid; 
	int cnt = 1; 
	for (int i = 0; i < n; i++) {
		if (v[i] <= mid) {
			mid -= v[i]; 
		}
		else {
			mid = temp; 
			cnt++; 
			if (v[i] > mid)return false; 
			else
			mid -= v[i]; 
		}
	}
	return cnt <= m; 
}


int main() {	
	cin >> n >> m; 
	for (int i = 0; i < n; i++) {
		int a; cin >> a; 
		v.push_back(a); 
	}
	int l, h; 
	l = 1; h = 987654321;
	int result = 0; 
	while (l <= h) {
		int mid = (l + h) / 2;
		if (check(mid)) {
			h = mid - 1; 
			result = mid; 
		}
		else {
			l = mid + 1; 
		}
	}
	cout << result; 
}

6236번: 용돈 관리