[G2] 백준 2632번 피자판매 C++ 누적합, 해시맵

리뷰

 

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

문제를 쉽게 접근했다가 피자가 원형꼴이라는 것에 대한 처리에 애를 먹은 문제

 

 

전역 변수

없음

 

 

함수

1. get_slices

void get_slices(vector<int>& pizza, unordered_map<int, int>& dic, int size, int k) {
	vector<int> prefix(2 * size + 1, 0);
	for (int i = 0; i < 2 * size; i++) {
		prefix[i + 1] = prefix[i] + pizza[i % size];
	}

	int total = prefix[size];
	if (total <= k) dic[total]++;

	for (int len = 1; len < size; len++) {
		for (int start = 0; start < size; start++) {
			int sum = prefix[start + len] - prefix[start];
			if (sum <= k) dic[sum]++;
		}
	}
}

 

피자의 연속된 구간합을 구하기 위한 함수

 

 

문제풀이

1. k, n, m에 값을 입력 받고, 벡터 a를 n크기로, b를 m크기로 초기화 한다. 해시맵 A, B도 초기화 해준다.
2. a, b에 각각 n, m개의 요소를 입력 받아 저장해 준다.
3. get_slices함수에 a, b와 관련된 요소들을 매개변수로 전달하여 호출해 준다.
4. get_slices함수는 조각의 길이들 pizza, 해시맵 dic, 조각의 개수 size, 고객이 원하는 크기 k를 전달 받는다.
5. 선형이 아닌 원형 누적합을 구해야 하기 때문에 벡터 prefix를 2*size+1크기로 초기화 해준다.
6. 2*size만큼 순회하며 prefix[i+1]을 prefix[i] + pizza[i&size]값으로 저장해 준다.
7. 변수 total에 피자의 최대 크기를 저장해 주고, total이 k이하라면 dic[total]의 값을 증가시킨다.
8. 조각의 개수를 1~size-1개를 순회하는 for문을 개행하고, 시작 지점을 0~size-1로 수행하는 2중 for문을 개행한다.
9. 피자를 원형으로 순회하며 변수 sum에 길이가 len인 조각의 길이를 저장하고, k이하라면 dic[sum]을 증가시킨다.
10. A, B피자에 대한 누적합을 구한 후엔 변수 ans를 0으로 초기화해 준다.
11. ans에 A[k], B[k]를 더해주고, A를 순회하며 k - key값을 만족하는 값이 B에 존재한다면 A개수 * B개수 만큼 곱해주어 ans에 더해준다.
12. ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

1. 초기엔 누적합 정보를 set에 저장하여 upper_bound - lower_bound를 처리해 주는 방식으로 접근했다.
2. 하지만 set는 연속된 자료구조가 아니라 이터레이터간 뺄셈이 불가능해 vector에 저장하고 정렬해 주었다.
3. 하지만 누적합을 처리할 때 원형이 아닌 선형 방식으로 저장해 주어 4%에서 Fail을 받았다.
4. 원형 누적합을 각 해시맵에 저장 후 개수를 찾아 곱해주는 방식으로 구현하니 AC를 받았다.

 

참고 사항

1. 누적합 배열의 크기를 각 피자 개수의 2배+1로 초기화 하고, 모듈러 연산을 통해 원형 누적합을 구해줘야 한다.
2. 현재는 두 해시맵을 모두 순회하며 개수를 곱해주는 방식을 차용했다.
3. 하지만 두 피자 중 조각의 개수가 적은 것을 순회하며 다른 피자의 upper_bound - lower_bound를 사용해 주면 더 적은 시간 복잡도로 문제를 해결할 수 있어 보인다.

 

정답 코드

#include<iostream>
#include<vector>
#include<unordered_map>
#define ll long long
using namespace std;

void get_slices(vector<int>& pizza, unordered_map<int, int>& dic, int size, int k) {
	vector<int> prefix(2 * size + 1, 0);
	for (int i = 0; i < 2 * size; i++) {
		prefix[i + 1] = prefix[i] + pizza[i % size];
	}

	int total = prefix[size];
	if (total <= k) dic[total]++;

	for (int len = 1; len < size; len++) {
		for (int start = 0; start < size; start++) {
			int sum = prefix[start + len] - prefix[start];
			if (sum <= k) dic[sum]++;
		}
	}
}

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

	int k, n, m;
	cin >> k >> n >> m;
	vector<int> a(n), b(m);
	unordered_map<int, int> A, B;

	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < m; i++) cin >> b[i];
	
	get_slices(a, A, n, k);
	get_slices(b, B, m, k);

	ll ans = 0;
	if (A[k]) ans += A[k];
	if (B[k]) ans += B[k];
	for (auto& d : A) {
		int need = k - d.first;
		if (need > 0 && B[need]) {
			ans += (ll)d.second * B[need];
		}
	}
	cout << ans;
}