백준 2632 피자판매 C++

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

2632번: 피자판매

map 자료구조를 이용해 풀었습니다. 피자를 n^2으로 start 번호부터 piece개 (정확히는 piece + 1개)를 돌면서 합을 구해줍니다. 그리고 map에 해당 합의 값을 찾아 +1 을 해줍니다. 

최종적으로 맵 중 하나를 골라 iterator를 돌리면서 나머지 피자의 양을 다른 맵에서 찾아줍니다.

 

벡터에 넣고 바이너리 서치를 해도 될 거 같지만 map을 이용해도 풀릴 것 같아 풀어보았습니다.

뭔가 키 값을 계속해서 찾아줘야하기 때문에 시간초과에 간당간당할 것 같았는데 시간 안에는 들어왔습니다. 

(대략적으로 find 할 때 log n 정도 걸리니 (맵이 트리 구조로 이루어짐) n^2 log n 정도 걸림. 따라서 총 복잡도는 대략 2 * n^2 * log n + n * log n => n^2 log n 정도, n이 최대 1000 이지만 find 할 때 항상 log n 나오는 건 아니므로 가능할 것으로 예상되었음)

 

코드는 다음과 같습니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

int pizza; // 구매하려는 피자 크기 
int m, n; // 조각 m, n개 

map<int,int> A; // 피자 A {크기 합:개수}
map<int,int> B; // 피자 B 

vector<int> vecA; // 피자 A 
vector<int> vecB; // 피자 B 

void init()
{
    cin >> pizza;
    cin >> m >> n;
    
    int num;
    vecA.resize(m);
    vecB.resize(n);
    
    int total = 0;
    for(int i = 0; i < m; i++) {
        cin >> num;
        vecA[i] = num;
        total += num;
    }
    A.insert({total, 1});
    
    total = 0;
    for(int i = 0; i < n; i++) {
        cin >> num;
        vecB[i] = num;
        total += num;
    }
    B.insert({total, 1});
}

void makeMap()
{
    // 모든 조각 합치는 건 처음에 포함 
    int sum, start, piece;
    for(start = 0; start < m; start++) {
        sum = 0;
        for(piece = 0; piece < (m - 1); piece++) {
            sum += vecA[(start + piece) % m];
            A[sum]++; // 키 없으면 A[sum] 초기값 (0) 들어가고 +1
        }
    }
    
    for(start = 0; start < n; start++) {
        sum = 0;
        for(piece = 0; piece < (n - 1); piece++) {
            sum += vecB[(start + piece) % n];
            B[sum]++;
        }
    }
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    init();
    makeMap();
    
    int result = 0;
   
    result += A[pizza];
    result += B[pizza];
    
    // 섞어 만드는 경우 
    auto iterA = A.begin();
    while(iterA != A.end()) {
        int pizzaA = iterA->first;
        int pizzaB = pizza - pizzaA;
        result += A[pizzaA] * B[pizzaB];
        iterA++;
    }
    
    cout << result;
}