[G3] 백준 17951번 흩날리는 시험지 속에서 내 평점이 느껴진거야 C++ 이분 탐색, 매개 변수 탐색

리뷰

 

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

시험지를 k개로 그룹화하고, 합이 가장 작은 그룹의 합이 최대가 되는 케이스를 찾는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 저장할 상수 변수
• n : 시험지의 개수를 저장할 변수
• k : 그룹의 수를 저장할 변수
• lst : 시험지의 맞은 문제 수를 저장할 배열

 

함수

없음

 

 

문제풀이

1. n, k값을 입력 받고, 변수 r을 0으로 초기화한다.
2. n개의 시험지의 맞은 개수를 lst에 저장하고, 맞은 개수를 r에 더해준다.
3. 변수 l을 0, ans를 0으로 초기화한다.
4. l이 r이하일 경우를 조건으로 하는 while문을 수행한다.
5. 변수 mid를 (l+r)/2로 초기화하고, 변수 sum, cnt를 0으로 초기화한다.
6. n개의 시험지를 순회하며 sum에 현재 시험지의 맞은 개수를 더해준다.
7. 만약 sum이 mid이상이 된 경우 cnt를 증가시키고, sum을 0으로 초기화한다.
8. cnt가 k개 이상일 경우 ans에 mid를 저장하고, l을 mid+1로 저장한다.
9. cnt가 k개 미만일 경우 r을 mid-1로 저장한다.
10. 모든 탐색을 마친 후 ans에 저장된 값을 출력한다.

 

트러블 슈팅

1. 문제를 잘못 이해하여 그룹이 k개를 초과할 경우 break처리를 하여 WA를 받았다.
2. 그룹이 k개 이상이면서 전 그룹의 합이 mid이상일 경우를 갱신 포인트로 잡아 AC를 받았다.

 

참고 사항

1.  (1 ≤ K ≤ N ≤ 10^5), (0 ≤ x ≤ 20) 정답이 int범위 이내이다.

 

정답 코드

#include<iostream>
using namespace std;

const int N = 1e5;
int n, k;
int lst[N];

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

	cin >> n >> k;
	int r = 0;
	for (int i = 0; i < n; ++i) {
		cin >> lst[i];
		r += lst[i];
	}

	int l = 0, ans = 0;
	while (l <= r) {
		int mid = (l + r) / 2;

		int sum = 0, cnt = 0;
		for (int i = 0; i < n; ++i) {
			sum += lst[i];
			if (sum >= mid) {
				++cnt;
				sum = 0;
			}
		}

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