[BOJ/백준 2632/C++] 피자판매

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

2632번: 피자판매

[문제 요약]

- 고객이 두 종류의 피자 A와 B를 취급하는 피자가게에서 피자를 주문하고자 한다. <그림 1>과 같이 각 종류의 피자는 다양한 크기의 여러 개의 피자조각으로 나누어져 있다. 각 조각에 쓰여진 숫자는 피자조각의 크기를 나타낸다.

<그림 1>

- 고객이 원하는 피자의 크기를 이야기하면, 피자가게에서는 한 종류의 피자를 2 조각 이상 판매할 때는 반드시 연속된 조각들을 잘라서 판매한다.

- 이때 판매한 피자조각의 크기 합이 주문한 크기가 되어야 한다. 판매한 피자조각은 모두 A종류이거나, 모두 B종류이거나, 또는 A와 B 종류가 혼합될 수 있다.

- 예를 들어서, <그림 1> 과 같이 잘라진 피자가 있을 때, 손님이 전체 크기가 7 인 피자를 주문하면, 피자 가게에서는 <그림2>와 같이 5 가지 방법으로 피자를 판매할 수 있다.

<그림 2>

- 피자가게에서 손님이 원하는 크기의 피자를 판매하는 모든 방법의 가지 수를 계산하는 프로그램을 작성하시오

 

[문제 조건]

- 첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다.

- 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n ≤ 1000).

- 세 번째 줄부터 차례로 m 개의 줄에는 피자 A의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다. 그 다음 n 개의 줄에는 차례로 피자B의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다.

- 각 종류의 피자조각의 크기는 시계방향으로 차례로 주어지며, 각 피자 조각의 크기는 1000 이하의 자연수이다.

- 시간 제한 : 2초

- 메모리 제한 : 128MB

 

[문제 풀이]

문제 태그가 누적합이랑 이분탐색이 있어서 두개를 이용해서 접근해볼려 했는데 마땅한 방법이 떠오르지 않아 마이웨이로 한번 풀어보기로 했다.

 

먼저 손님이 원하는 피자의 크기를 K라고 하자.

 

그러면 (A피자에서 선택한 조각의 합, B피자에서 선택한 조각의 합) (i,j) 의 형태로 (0, K) , (1, K-1), (2, K-2) ... (K-1 , 1) , (K, 0)의 경우를 모두 구해주는 방법을 사용했다.

 

이때 각 피자의 조각의 개수가 최대 1천개이여서 모든 조각의 경우의 수를 구해도 시간적으로 충분하다.

 

그리고 각 피자 조각의 크기가 최대 1천이라 조각의 합이 최대 100만이다. 따라서 100만개짜리 vector를 각각 하나씩 만들어 조각의 합에따라 값을 하나씩 증가시키는 방법을 사용하였다. 

 

물론 이 부분에서 map을 이용하는 방법도 있겠지만 map을 써보니 오히려 더 시간이랑 메모리를 더 잡아먹는다.

 

가능한 조각의 합의 개수들을 모두 구했으면 답은 다음과 같이 구할 수 있다.

• A피자에서 조각의 크기의 합을 i , B피자에서 조각의 크기의 합을 j 라 할때 i + j = K 다.
• i와 j 모두 0이 아닐 때 i * j 의 값을 ans에 더해준다.
• i와 j 둘 중 하나라도 0이면 둘 중 0이 아닌 값을 ans에 더해준다.

[소스 코드]

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

#define INF 987654321
#define pii pair<int,int>

using namespace std;

int K, n, m;
vector<int> A;
vector<int> A_piece;
vector<int> B;
vector<int> B_piece;

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

	cin >> K >> n >> m;

	A_piece.resize(1000 * 1000 + 1);
	B_piece.resize(1000 * 1000 + 1);

	int tmp;
	for (int i = 0; i < n; i++) { cin >> tmp; A.push_back(tmp); }
	for (int i = 0; i < m; i++) { cin >> tmp; B.push_back(tmp); }

	//A피자의 모든 경우 구하기
	for (int i = 0; i < n; i++)
	{
		int sum = 0;
		for (int j = 0; j < n - 1; j++)
		{
			sum += A[(i + j) % A.size()];
			A_piece[sum]++;
		}
	}
	//B피자의 모든 경우 구하기
	for (int i = 0; i < m; i++)
	{
		int sum = 0;
		for (int j = 0; j < m - 1; j++)
		{
			sum += B[(i + j) % B.size()];
			B_piece[sum]++;
		}
	}

	int sum = 0;
	for (int i = 0; i < n; i++) sum += A[i];
	A_piece[sum]++; sum = 0;
	for (int i = 0; i < m; i++) sum += B[i];
	B_piece[sum]++;


	int ans = 0;
	for (int i = 1; i <= K - 1; i++)
	{
		ans += A_piece[i] * B_piece[K - i];
	}
    //A피자만 고른경우 , B피자만 고른 경우를 따로 더해준다.
	cout << ans + A_piece[K] + B_piece[K];
}

각 피자 별로 모든 경우를 구할때 n-1개, m-1개의 합만 구하는 이유는 n,m개를 모두 다 더 하는 경우는 중복이 발생할 수 있기 때문에 따로 한번만 계산해주었다.

위의 경우는 map을 이용했을 때, 아래는 vector를 이용했을 때

굳