[알고리즘] 백준2632 피자판매

문제

백준2632 피자판매

구상

손님이 주문한 피자를 판매하는 경우의 수는 다음과 같다.

1. A 피자로만 구성
2. B 피자로만 구성
3. A 피자와 B 피자 혼합

먼저 위 경우의 수의 최대값을 알아보자.

1. A와B 피자는 최대 1000 조각이다.
2. 손님은 최대 2,000,000 피자만큼 주문 할 수 있다.

• 2,000,000 피자를 주문했을 경우
  • (A,B) -> (1 , 1,999,999),(2 , 1,999,998) ~ (1,999,999 , 1)
  • 위 경우의 수 만큼 A와B 피자의 경우의 수를 확인해보아야 한다.

경우의 수 만큼 A와 B 피자의 경우의 수를 확인하려면 시간초과가 발생한다.

코드

#include<bits/stdc++.h>
using namespace std;
int p,m,n,ret;
int a[1001],b[1001];
map<int ,int> aCnt, bCnt;

void pizza(int n, int arr[], int target, map<int,int> &mp){
	for(int i=0; i<n; i++){ 
		int total = 0,idx = i, cnt =0;
		while(total<target){ // target 보다 total 이 커지면 탐색할 필요가 없음
			// i번째 index 부터 탐색 
			if(idx == n) idx = 0; // 배열 연속 탐색 
			if(cnt == n) break; // 배열을 한바퀴 돌았다면 break
			total += arr[idx]; // 탐색값을 total에 저장 
			++mp[total]; // total에 해당하는 key를 가지는 value ++ (경우의 수) 
			if(cnt == n-1) mp[total] = 1; 
			++idx;
			++cnt;
		}
	}
} 

void combi(){ // 조합 가능한 모든 경우의 수 더해줌 
	for(int i=1; i<p; i++){
		ret += aCnt[i]*bCnt[p-i];
	}
}

int main(){
	// 입력 
	cin>>p;
	cin>>m>>n;
	for(int i=0; i<m; i++){
		cin>>a[i];
	}
	for(int i=0; i<n; i++){
		cin>>b[i];
	}
	
	// A 피자의 경우의 수 기록 
	pizza(m,a,p,aCnt);
	
	// B 피자의 경우의 수 기록 
	pizza(n,b,p,bCnt);
	ret += aCnt[p];
	ret += bCnt[p];
	combi();
	cout<<ret<<'\n';
	 
	return 0;
}

A와 B의 경우의 수를 미리 map에 저장한 후 조합 가능한 경우의 수를 더해준다.

if(cnt == n-1) mp[total] = 1;

를 해준 이유는

6
3 3
111
111

위의 입력이 들어왔을때, 전체 총합이 target인 경우 각 원소를 돌며 중복으로 경우의 수를 갱신하기 때문에 이를 방지하기 위함이다.

해당 코드가 없으면 9의 잘못된 정답이 나온다.