[G2] 백준 2613번 숫자구슬 C++ 이분 탐색, 매개 변수 탐색

 

리뷰

 

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

파라매트릭 서치 문제는 항상 다 온 것 같으면서도 사소한 디테일이 어려운 것 같다.

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 숫자 구슬의 개수를 저장할 변수
• m : 만들어야 할 숫자 구슬 그룹의 개수를 저장할 변수
• arr : 숫자 구슬 값을 저장하기 위한 배열

 

함수

없음

 

 

문제풀이

1. n, m값을 입력 받고, 변수 l, r을 전부 0으로 초기화한다.
2. n개의 구슬 정보를 입력 받아 arr배열을 초기화 하고, r은 각 구슬의 합, l은 각 구슬의 최대값으로 저장한다.
3. 변수 mn을 r로, 정수형 벡터 path를 초기화한다.
4. l이 r이하일 경우를 조건으로 하는 while루프를 수행한다.
5. 변수 mid를 l+r을 2로 나눈 몫으로 저장한다.
6. 정수형 벡터 g와, 변수 sum, cnt를 0으로 초기화한다.
7. n개의 구슬을 순회하며 sum+arr[i]가 mid보다 클 경우 g에 cnt를 push, cnt를 1로 초기화, sum을 arr[i]로 변경한다.
8. sum+arr[i]가 mid이하일 경우 sum에 arr[i]를 더하고, cnt를 증가시킨다.
9. for문을 빠져나오며 g에 cnt를 마저 push해준다.
10. g의 크기가 m보다 크다면 l을 mid+1로 변경한다.
11. g의 크기가 m이하라면, g의 size를 m으로 맞춰주는 평탄화 작업을 수행하고, r을 mid-1로, path를 g로, mn을 mid로 변경한다.
12. 모든 탐색을 마친 후 mn을 출력 후 개행문자를 삽입하여 줄바꿈을 수행한다.
13. path내부 요소를 공백을 기준으로 출력한다.

 

트러블 슈팅

1. g의 크기가 m보다 작을 경우 크기를 m으로 만들어주는 평탄화 작업을 수행하지 않아 WA를 받았다.
2. l의 하한값을 정해주지 않아, cnt가 0인 경우에도 push가 되는 경우가 존재하여 WA를 받았다.
3. g의 크기를 m으로 평탄화 작업을 해주고, 구슬의 값을 입력 받을때 l의 하한값을 명시해 주어 AC를 받았다.

 

참고 사항

1. 그룹에 포함된 숫자 구슬의 개수는 0보다 커야 한다.
2. 만약 그룹의 합의 최댓값이 최소가 되도록 하는 경우가 둘 이상이라면 그 중 하나만을 출력한다.

 

정답 코드

#include<iostream>
#include<vector>
using namespace std;

const int N = 300;
int n, m;
int arr[N];

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

	cin >> n >> m;
	int l = 0, r = 0;
	for (int i = 0; i < n; ++i) {
		cin >> arr[i];
		r += arr[i];
		l = max(l, arr[i]);
	}
	
	int mn = r;
	vector<int> path;
	while (l <= r) {
		int mid = (l + r) / 2;

		vector<int> g;
		int sum = 0, cnt = 0;
		for (int i = 0; i < n; ++i) {
			if (sum + arr[i] > mid) {
				g.push_back(cnt);
				cnt = 1;
				sum = arr[i];
			}
			else {
				sum += arr[i];
				++cnt;
			}
		}
		g.push_back(cnt);

		if (g.size() > m) l = mid + 1;
		else {
			int idx = g.size() - 1;
			while (g.size() < m && idx >= 0) {
				if (g[idx] == 1) {
					--idx;
					continue;
				}
				--g[idx];
				g.push_back(1);
			}
			r = mid - 1;
			path = g;
			mn = mid;
		}
	}

	cout << mn << "\n";
	for (int i : path) cout << i << " ";
}