BOJ 2632번 피자판매

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

github : https://github.com/junho0956/Algorithm/blob/master/2632/2632/%EC%86%8C%EC%8A%A4.cpp

 

문제는 이런식으로 접근해볼 수 있다.

'반드시 연속된 조각' 에서 연속된 부분합에 대한 부분집합이 필요하다

피자는 원형이기때문에 마지막 조각이 첫번째 조각과 연속될 수 있다

각각의 피자에 대한 부분집합을 안다면 이분탐색을 이용하여 경우의 수를 찾을 수 있다

 

연속된 부분합에 대한 부분집합은 범위가 1000 이기 때문에 완전탐색으로도 충분히 구해낼 수 있다

아래 코드에서 makeA, makeB 함수는 완전탐색을 통해 만들어낼 수 있는 부분집합을 구하는 과정인데

범위는 피자의 조각보다 -1 작은 범위까지만 구하고, 마지막에 전체 합에 대한 값만 추가해주면 된다

 

이분탐색을 위해서는 정렬은 필수이고,

 

모든 경우의 수는 피자A, 피자B 각판에서 만들어낼 수 있는 경우의수 + (A+B) 로 만들 수 있는 경우의 수

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
typedef long long ll;
ll cnt;
 
// m,n 의 최대범위는 1000
// 연속된 조각을 판매해야하기 때문에, 원형을 고려해서 2배로 잡는다
int arra[2001], arrb[2001];
vector<int> a, b;
int m, n, k;
 
void makeA(int idx, int len){
    if (len == m) return;
 
    int sum = 0;
    for (int i = idx; i < idx + len; i++) sum += arra[i];
    if (sum == k) cnt++;
    a.push_back(sum);
 
    makeA(idx, len + 1);
}
 
void makeB(int idx, int len) {
    if (len == n) return;
 
    int sum = 0;
    for (int i = idx; i < idx + len; i++) sum += arrb[i];
    if (sum == k) cnt++;
    b.push_back(sum);
 
    makeB(idx, len + 1);
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> k >> m >> n;
    for (int i = 0; i < m; i++) cin >> arra[i], arra[m+i] = arra[i];
    for (int i = 0; i < n; i++) cin >> arrb[i], arrb[n+i] = arrb[i];
 
    // 각 가능한 모든 부분집합의 합들을 구한다
    for (int i = 0; i < m; i++) makeA(i, 1);
    for (int i = 0; i < n; i++)    makeB(i, 1);
    
    // 전체 합을 따로 구한다
    int sum = 0;
    for (int i = 0; i < m; i++) sum += arra[i];
    if (sum == k) cnt++;
    a.push_back(sum), sum = 0;
    for (int i = 0; i < n; i++) sum += arrb[i];
    if (sum == k) cnt++;
    b.push_back(sum);
 
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
 
    // 원하는 피자양을 만들 수 있는 범위를 이분탐색을 이용하여 찾는다
    for (int i = 0; i < b.size(); i++) {
        int res = k - b[i];
        ll lower = lower_bound(a.begin(), a.end(), res) - a.begin();
        ll upper = upper_bound(a.begin(), a.end(), res) - a.begin();
        cnt += upper - lower;
    }
 
    cout << cnt;
    return 0;
}