[백준/BOJ] 백준 2632번 : 피자판매

www.acmicpc.net/problem/2632

2632번: 피자판매

A피자 연속 부분의 모든 경우를 구하고, B피자 연속 부분의 모든 경우를 구한 뒤, 정렬을 해서 A피자 연속 부분(partA)을 모두 확인하며 B피자 연속 부분(partB)의 값 중 합이 손님이 구매하고자 하는 피자 크기인 것의 개수를 구하여 문제를 해결한다. 이때 lower_bound와 upper_bound를 통해 문제를 해결했다.

 

코드

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

int want_size;
int m, n;
vector<int> A;
vector<int> B;
vector<int> partA; //A피자 연속 부분의 모든 경우
vector<int> partB; //B피자 연속 부분의 모든 경우
vector<int>::iterator it1;
vector<int>::iterator it2;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> want_size;
	cin >> m >> n;

	for (int i = 0; i < m; i++)
	{
		int input;
		cin >> input;

		A.push_back(input);
	}

	for (int i = 0; i < m - 1; i++)
	{
		A.push_back(A[i]);
	}

	for (int i = 0; i < n; i++)
	{
		int input;
		cin >> input;

		B.push_back(input);
	}

	for (int i = 0; i < n - 1; i++)
	{
		B.push_back(B[i]);
	}

	partA.push_back(0); //A피자에서 아무것도 안고르는 경우
	for (int i = 0; i < m; i++)
	{
		int sum = 0;
		for (int j = i; j < i + m - 1; j++)
		{
			sum += A[j];
			partA.push_back(sum);
		}

		if (i == 0) //전체 피자 한판의 경우를 포함하기 위해 (한가지만 넣기 위해)
		{
			sum += A[m - 1];
			partA.push_back(sum);
		}
	}

	partB.push_back(0); //B피자에서 아무것도 안고르는 경우
	for (int i = 0; i < n; i++)
	{
		int sum = 0;
		for (int j = i; j < i + n - 1; j++)
		{
			sum += B[j];
			partB.push_back(sum);
		}

		if (i == 0) //전체 피자 한판의 경우를 포함하기 위해 (한가지만 넣기 위해)
		{
			sum += B[n - 1];
			partB.push_back(sum);
		}
	}

	sort(partA.begin(), partA.end());
	sort(partB.begin(), partB.end());

	int result = 0;

	for (int i = 0; i < partA.size(); i++)
	{
		int find_size = want_size - partA[i];

		it1 = lower_bound(partB.begin(), partB.end(), find_size);
		it2 = upper_bound(partB.begin(), partB.end(), find_size);

		//찾았을 경우
		if (it1 != partB.end() && (*it1) == find_size)
			result += (it2 - it1);
	}

	cout << result;

	return 0;
}