취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 20917번 문제인 흩날리는 시험지 속에서 내 평점이 느껴진거야이다.
문제는 아래 링크를 확인하자.

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

어떤 고정된 값 \(x\)이 주어질 때 시험지를 \(x\)점 이상의 \(K\)개 그룹으로 나눌 수 있는지 판단하는 것은 그리디한 접근으로 어렵지 않게 해낼 수 있다. 또한 \(x\)의 값이 커질 때 그룹으로 나눌 수 없었다가 나눌 수 있게 되는 경우는 일어날 수 없으며, 마찬가지로 \(x\)의 값이 작아질 때 그룹으로 나눌 수 있었다가 나눌 수 없게 되는 경우는 일어날 수 없다는 점을 관찰할 수 있다.

위의 관찰을 이용하면 문제에서 구하고자하는 점수는 이분탐색을 통해 얻을 수 있음을 알 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N, K;
int A[100000];
int L = 0, R = 2000000;

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

	cin >> N >> K;
	for (int i = 0; i < N; i++) cin >> A[i];
	while (L < R) {
		int mid = (L + R) / 2 + 1;
		int cnt = 0, val = 0;
		for (int i = 0; i < N; i++) {
			val += A[i];
			if (val >= mid) cnt++, val = 0;
		}
		if (cnt < K) R = mid - 1;
		else L = mid;
	}

	cout << L;
}