[BOJ / C++] 17951 : 흩날리는 시험지 속에서 내 평점이 느껴진거야

링크

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

17951번: 흩날리는 시험지 속에서 내 평점이 느껴진거야

 

풀이 과정

강의에서 설명했던 파라메트릭 서치 문제인 듯 하다. 이 문제를 통해서 이분 탐색을 어떻게 적용시켜서 문제를 해결할 지 감을 잡을 수 있게 됐다.

 

우선 그룹을 나눌 기준 점수가 mid이다. 이 기준값(mid)대로 나눴을 때 그룹의 수가 K개 이상이면 기준값이 작다는 뜻이므로 left를 mid + 1로 이동한다. K개 이하라면 기준값이 크다는 뜻이므로 right를 mid - 1로 이동한다.

최초의 right 값의 경우, 시험지의 점수를 입력을 받을 때 벡터에 저장함과 동시에 그 값들의 총합을 sum 변수에 저장해서 이 값을 right로 이용했다.

그리고 mid값을 기준으로 그룹을 나눴을 때 K개 이상인지 확인하는 calc()함수를 만들어서 조건문에 활용했고, 이 때의 mid값을 ans 변수에 저장해서 정답을 확인할 수 있도록 만들었다.

최종적으로 그룹이 K개 이상이 될 때의 기준값이 정답이 되므로 ans를 출력하면 된다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

int N, K;
int sum = 0;
vector<int> x;

bool calc(int mid) {
	int count = 0;
	int s = 0;

	for (int i = 0; i < N; i++) {
		s += x[i];
		if (s >= mid) {
			count++;
			s = 0;
		}
	}

	return count >= K;
}

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

	cin >> N >> K;
	x = vector<int>(N, 0);

	for (int i = 0; i < N; i++) {
		int input;
		cin >> input;

		x[i] = input;
		sum += input;
	}

	int left = 0, right = sum;
	int ans = 0;
	while (left <= right) {
		int mid = (left + right) / 2;
		if (calc(mid)) {
			ans = mid;
			left = mid + 1;
		}
		else right = mid - 1;

	}

	cout << ans;

	return 0;
}