2632번_피자판매_BOJ

문제 링크

2632번 피자판매 : https://www.acmicpc.net/problem/2632

문제 설명 및 해결 아이디어

가능한 모든 방법의 가지 수를 계산하는 문제이다.

피자는 붙어있는 경우에만 합칠 수 있기때문에 이중포문을 이용해서 합칠 수 있는 경우의 크기만 apizz, bpizz벡터에 넣어주었다. 

손님이 주문한 크기와 똑같은 크기의 조각이 있을 수 있으므로, A, B 두 종류의 피자에서 주문한 크기와 똑같은 것들은 먼저 count를 해준다.

그 후 A피자에서 나올 수 있는 모든 크기를 탐색하면서, B피자중에 나올 수 있는 크기와의 합이 손님이 주문한 피자의 크기가 나오는 것이 있으면 count해주면 된다.

코드

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int order, m, n, num, ta, tb;
vector<int> ap, bp, apizz, bpizz;
int main() {
    scanf("%d %d %d", &order, &m, &n);
    
    for (int i = 0; i < m; ++i) {
        scanf("%d", &num);
        ap.push_back(num);
        ta += num;
    }
 
    for (int i = 0; i < n; ++i) {
        scanf("%d", &num);
        bp.push_back(num);
        tb += num;
    }
 
    for (int i = 0; i < m; ++i) {
        int psum = 0;
        for (int j = i; j < m + i - 1; ++j) {
            psum += ap[j%m];
            apizz.push_back(psum);
        }
    }
    apizz.push_back(ta);
 
    for (int i = 0; i < n; ++i) {
        int psum = 0;
        for (int j = i; j < n + i - 1; ++j) {
            psum += bp[j%n];
            bpizz.push_back(psum);
        }
    }
    bpizz.push_back(tb);
 
    sort(apizz.begin(), apizz.end());
    sort(bpizz.begin(), bpizz.end());
 
    int res = 0;
    res += upper_bound(apizz.begin(), apizz.end(), order) - lower_bound(apizz.begin(), apizz.end(), order);
    res += upper_bound(bpizz.begin(), bpizz.end(), order) - lower_bound(bpizz.begin(), bpizz.end(), order);
 
    for (int i = 0; i < apizz.size(); ++i) {
        if (apizz[i] >= order)
            break;
        int r = order - apizz[i];
        res += upper_bound(bpizz.begin(), bpizz.end(), r) - lower_bound(bpizz.begin(), bpizz.end(), r);
    }
 
    printf("%d\n", res);
    return 0;
}