[백준문제풀이] 2632 피자판매

 

풀이일시 : 2020-12-26

 

 

문제 : 

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

고객이 원하는 피자의 크기를 이야기하면, 피자가게에서는 한 종류의 피자를 2 조각 이상 판매할 때는 반드시 연속된 조각들을 잘라서 판매한다. 이때 판매한 피자조각의 크기 합이 주문한 크기가 되어야 한다. 판매한 피자조각은 모두 A종류이거나, 모두 B종류이거나, 또는 A와 B 종류가 혼합될 수 있다. 예를 들어서, <그림 1> 과 같이 잘라진 피자가 있을 때, 손님이 전체 크기가 7 인 피자를 주문하면, 피자 가게에서는 <그림2>와 같이 5 가지 방법으로 피자를 판매할 수 있다.

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

 

 

입력 : 

첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n ≤ 1000). 세 번째 줄부터 차례로 m 개의 줄에는 피자 A의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다. 그 다음 n 개의 줄에는 차례로 피자B의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다. 각 종류의 피자조각의 크기는 시계방향으로 차례로 주어지며, 각 피자 조각의 크기는 1000 이하의 자연수이다.

 

 

출력 : 

첫째 줄에는 피자를 판매하는 방법의 가지 수를 나타내는 정수를 출력한다. 피자를 판매하는 방법이 없는 경우에는 숫자 0을 출력한다.

 

 

풀이 :

투포인터 알고리즘으로 풀이한다.

 

다른 투포인터 알고리즘 문제와 다른점이였던 점은 피자가 원형이고 부분수열이 아닌 이어져있는 조각만을 판매하는 것이기 때문에

 

만들 수 있는 피자의 크기를 전부 구해놓는 hap 함수에서 sum 하는 피자의 갯수를 유의해 주어야한다.

 

dbstndi6316.tistory.com/39

[개념정리] Two pointer algorithm

 

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

const int MAX = 1000;

int N;
int a, b;
int N1[MAX];
int N2[MAX];
vector <int> pizza1;
vector <int> pizza2;
int c, c1, c2;

vector<int> hap(int arr[],int val) {
	int sum = 0;
	vector<int>ret;
	for (int i = 0; i < val; i++) {
		for (int j = i; j < i+val-1; j++) {
			sum += arr[j%val];
			ret.push_back(sum); //
		}
		sum = 0;
	}
	ret.push_back(0); //0 push
	for (int i = 0; i < val; i++) {
		sum += arr[i];
	}
	ret.push_back(sum); //전체 더한거 push
	return ret;
}

void twopointer() {
	int pointer1 = 0, pointer2 = 0;
	while (pointer1 < pizza1.size() && pointer2 < pizza2.size()) {
		c1 = 0, c2 = 0;
		int result = pizza1[pointer1] + pizza2[pointer2];
		if (result == N) {
			for (int t = pizza1[pointer1]; pointer1 < pizza1.size() && t == pizza1[pointer1]; c1++, pointer1++);
			for (int t = pizza2[pointer2]; pointer2 < pizza2.size() && t == pizza2[pointer2]; c2++, pointer2++);
			c += c1 * c2;
		}
		else if (result > N) {
			pointer2++;
		}
		else
			pointer1++;
	}
}

int main() {
	cin >> N;
	cin >> a >> b;
	for (int i = 0; i < a; i++) {
		cin >> N1[i];
	}
	for (int i = 0; i < b; i++) {
		cin >> N2[i];
	}

	pizza1 = hap(N1,a);
	pizza2 = hap(N2,b);
	//0도 더해주자 아예 포함안되는 경우도 있으니깐

	sort(pizza1.begin(), pizza1.end());
	sort(pizza2.begin(), pizza2.end(), greater<int>());

	twopointer();
	cout << c << endl;

	return 0;
}