C++ / 백준 / 2632 / 피자판매

문제

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

2632번: 피자판매

문제풀이

아래로 내리면 다시 푼 문제풀이가 있습니다.

A 피자의 연속된 부분집합의 합을 구하고 unordered_map에 저장한다.

연속된 부분집합은 메모이제이션을 이용해서 이중 반복문으로 구한다.

 

피자는 원형이기 때문에 경우의 수를 아래와 같은 방법으로 구했다.

idx1은 0부터 n-1까지, idx2는 합이 구하려는 조각보다 작다면 idx1의 바로 전 조각까지 구하도록 한다.

while (!(idx2 / m == 1 && idx2 % m == idx1))이 이 부분이다.

만약 m이 5, idx1 = 2이면 idx2는 3, 4, 0, 1의 인덱스를 탐색하면서 모든 경우의 수를 확인한다.

 

피자는 모두 A 조각이거나, 모두 B 조각이거나, 둘을 섞을 수 있고, 무조건 연속된 조각만 판매가 가능하다.

따라서 A 조각의 될 수 있는 경우의 수를 모두 탐색하면서 unordered_map인 pick에 저장을 해준다.

만약 A 조각 만으로 구성할 수 있다면 answer++을 한다.

그리고 위의 식은 A 피자의 전부를 구하는 경우가 m개의 경우만큼 나오므로

	if (sum_A == slice) answer++;
	else pick[sum_A]++;

전부를 구하는 경우는 한 번만 취급할 수 있도록 코드를 추가해 준다.

A 피자의 경우를 모두 확인했다면 B 피자의 경우를 확인해야 한다.

A 피자의 경우를 구하는 방법이랑 동일하게 한다.

대신 pick에 저장하지 않고 바로 answer에 A와 조합하여 만드는 경우를 더하거나 B 피자로만 만들 수 있으면 answer++을 한다.

 

코드

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int idx1(0), idx2(0);
	int m(0), n(0);
	int slice(0);

	cin >> slice;
	cin >> m >> n;

	unordered_map<int, int>pick;
	vector<int>A_pizza(m, 0);
	vector<int>B_pizza(n, 0);
	long long answer(0);

	for (idx1 = 0; idx1 < m; ++idx1)
		cin >> A_pizza[idx1];

	for (idx2 = 0; idx2 < n; ++idx2)
		cin >> B_pizza[idx2];

	int sum(0);

	int sum_A(accumulate(A_pizza.begin(), A_pizza.end(), 0));
	int sum_B(accumulate(B_pizza.begin(), B_pizza.end(), 0));

	if (sum_A == slice) answer++;
	else pick[sum_A]++;

	for (idx1 = 0; idx1 < m; ++idx1) {
		sum = 0;
		idx2 = idx1;
		while (!(idx2 / m == 1 && idx2 % m == idx1)) {
			sum += A_pizza[idx2 % m];
			if (sum > slice) break;
			else if (sum != sum_A) {
				if (sum == slice) {
					answer++;
					break;
				}
				else pick[sum]++;
			}
			++idx2;
		}
	}
	if (sum_B == slice) answer++;
	else answer += pick[slice - sum_B];

	for (idx1 = 0; idx1 < n; ++idx1) {
		sum = 0;
		idx2 = idx1;
		while (!(idx2 / n == 1 && idx2 % n == idx1)) {
			sum += B_pizza[idx2 % n];
			if (sum > slice) break;
			else if (sum != sum_B) {
				if (sum == slice) answer++;
				else answer += pick[slice - sum];
			}
			++idx2;
		}
	}

	cout << answer;
}

 

--------------------------------------------------------------------------------------------------------------------

피자 조각의 최대 크기는 1000이고 A의 최대 개수는 1000개 이므로 미리 1,000x1,000인 1,000,000개짜리 벡터를 만들어놓고 조각의 일부 크기를 구할때마다 크기에 해당하는 부분에 +1을 했다.

피자를 구하는 경우의 수는

1. A피자만으로 구성

2. B피자만으로 구성

3. A피자 전체와 B피자 일부로 구성

4. B피자 전체와 A피자 일부로 구성

5. A피자 전체와 B피차 전체로 구성

 

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
vector<int>part(1000001, 0);

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int order(0);
	cin >> order;
	int N(0), M(0);
	int idx(0), idx2(0);

	cin >> N >> M;

	vector<int>pizza_a(N, 0);
	vector<int>pizza_b(M, 0);

	for (idx = 0; idx < N; ++idx)
		cin >> pizza_a[idx];

	for (idx = 0; idx < M; ++idx)
		cin >> pizza_b[idx];

	long long cnt(0);

	for (idx = 0; idx < N; ++idx) {
		long long cur_size(0);
		for (idx2 = idx; idx2 + 1 < idx + pizza_a.size(); ++idx2) {
			cur_size += pizza_a[idx2 % pizza_a.size()];
			if (cur_size > order) break;
			else if (cur_size == order) cnt++;
			else part[cur_size]++;
		}
	}


	long long sum_A = accumulate(pizza_a.begin(), pizza_a.end(), 0);
	long long sum_B = accumulate(pizza_b.begin(), pizza_b.end(), 0);

	if (order >= sum_B)
		cnt += part[order - sum_B];

	if (sum_A == order) cnt++;
	else part[sum_A]++;



	for (idx = 0; idx < M; ++idx) {
		long long cur_size(0);
		for (idx2 = idx; idx2 + 1 < idx + pizza_b.size(); ++idx2) {
			cur_size += pizza_b[idx2 % pizza_b.size()];
			if (cur_size > order) break;
			else if (cur_size == order) cnt++;
			else cnt += part[order - cur_size];
		}
	}
	
	if (sum_B == order) cnt++;
	if (sum_A + sum_B == order) cnt++;

	cout << cnt;
}