[BOJ 6236] 용돈관리

풀이

총 사용할 수 있는 금액이 10억으로 꽤 큰 숫자이기 때문에 O(N)으로 풀이하면 시간초과가 난다. 그래서 logN의 동작으로 풀어야겠다고 생각하였고 이분탐색을 사용하면 풀 수 있을 것 같았다. 0~10억의 범위를 잡고 이분탐색으로 M번만 사용하는 최소 K를 갱신해가면서 찾으면 된다.

코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>

using namespace std;

int n, m;
vector<int> v(100001);

int main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);

	cin >> n >> m;

	for (int i = 0; i < n; i++) cin >> v[i];

	int l = *max_element(v.begin(), v.end());
	int r = 1000000000;
	int k = 0;
	while (l <= r) {
		int mid = (l + r) / 2;
		int i = 0;
		int cnt = 0;
		while (i < n) {
			int sum = 0;
			int value = mid;
			cnt++;
			while (i < n && v[i] <= value) {
				value -= v[i++];
			}
		}

		if (cnt <= m) {
			k = mid;
			r = mid - 1;
		}
		else l = mid + 1;

	}
	cout << k << '\n';

	return 0;
}