[BAE/<JOON> 문제풀이] 2613. 숫자 구슬

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

2613번: 숫자구슬

서론

파라메트릭. 게다가 판정이 그리디라 더 헷갈림. 근데 파라메트릭 문제들에 DP 태그는 왜 붙어있는지 잘 모르겠다.

풀이

그동안 풀었던 파라메트릭 문제들과 다를건 전혀 없다.

판정 로직이 메인인데 그리디하게 한계 합계까지 더하다가 합계 제한을 초과했을 때 그룹을 생성하고 그 수를 세는 방식이다.

한가지 다른 점은 이 문제는 정해진 그룹의 수를 반드시 만들어야하기 때문에 만약 그룹 수가 부족한 경우 1개 이상의 그룹에서 구슬을 분리하는 작업을 해줘야 한다. 이것 때문에 맞왜틀로 시간 좀 뭉갬..

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <string>
using namespace std;
using ll = long long;
vector<int> check(const vector<int>& arr, int val, int ccl) {
	int cs = 0; int cc = 0; int tcc = 0; vector<int> ret;
	for (int i = 1; i < arr.size(); i++) {
		if (arr[i] > val) return {};
		if (cs + arr[i] >= val) {
			if (++tcc > ccl) return {};
			if (cs + arr[i] == val) {
				ret.push_back(cc + 1);
				cs = 0; cc = 0;
			}
			else {
				ret.push_back(cc);
				cs = 0; cc = 0;
				i--;
			}
		}
		else {
			cs += arr[i];
			cc++;
		}
	}
	if (cc > 0) {
		ret.push_back(cc);
		if (++tcc > ccl) return {};
	}	
	return ret;
}

int main() {
	int n, m; cin >> n >> m; vector<int> arr(n + 1); int f = 1, r = 0;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		r += arr[i];
	}
	int dap = f; vector<int> dv;
	while (f <= r) {
		int mid = (f + r) / 2;
		auto vv = check(arr, mid, m);
		if (vv.size() > 0) {
			dap = mid; dv = vv;
			r = mid - 1;
		}
		else {
			dap = mid + 1;
			f = mid + 1;
		}
	}
	cout << dap << "\n"; vector<int> dpv;
	if (dv.size() < m) {
		int df = m - dv.size();
		for (int i = 0; i < dv.size(); i++) {
			if (dv[i] > 1) {
				int p = dv[i] - 1 < df ? dv[i] - 1 : df;
				dv[i] -= p;
				df -= p;
				dpv.push_back(dv[i]);
				for (int j = 0; j < p; j++) dpv.push_back(1);
			}
			else dpv.push_back(dv[i]);
		}
	}
	else dpv = dv;
	for (auto v : dpv) cout << v << " ";
	return 0;
}