백준 2632번 피자판매 - C++ 풀이

---

 

1. B피자에서 연속된 조각을 선택하는 모든 경우를 구해 각 연속합을 만들 수 있는 경우의 수를 구해둔다.
2. A피자에서 연속된 조각을 선택하는 모든 경우에 대해 목표합을 만들기 위한 경우의 수를 더한다.

 

1. B피자에서 연속된 조각을 선택하는 모든 경우를 구해 각 연속합을 만들 수 있는 경우의 수를 구해둔다.

 두 피자에서 연속된 조각을 선택하는 모든 경우를 고려하면 O(N^4)의 시간 복잡도가 소요된다. 따라서 두 피자를 각각 탐색한 뒤, A피자를 기준으로 대응하는 B 피자의 경우의 수를 구하는 방법을 사용하여 O(N^2)에 해결할 것이다.

 mp[i] = (B 피자에서 연속합이 i가 되도록 조각을 고르는 경우의 수)라고 하자. B 피자에서 연속된 조각을 선택하는 모든 경우에 대해 그 합을 구해 mp 배열을 구해둔다.

 

 

2. A피자에서 연속된 조각을 선택하는 모든 경우에 대해 목표합을 만들기 위한 경우의 수를 더한다.

 A피자에서 연속된 조각을 선택했을 때 합이 sumA이고 목표합은 P라고 하자. 전체합이 P가 되기 위해서는 B피자에서 합이 P-sumA가 되도록 조각을 골라야 하므로 이때의 경우의 수는 mp[P-sumA]이다. 이렇게 A 피자에서 연속된 조각을 선택하는 모든 경우에 대해 대응되는 B피자의 경우의 수를 구해 전부 더해주면 된다.

반응형

---

#include <iostream>
#include <map>

using namespace std;
typedef long long ll;

int P, M, N;
int A[1001], B[1001];
int sumA[1001][1001], sumB[1001][1001];     // sum[i][j] = i번 조각부터 j번 조각까지 구간합
map<int, int> mp;       // mp[i] = B피자로 연속합 i를 만드는 가짓수

void calcSum() {
    for (int s=0; s<M; s++) {
        for (int i=0; i<M; i++) {
            int e = (s+i)%M;
            sumA[s][e] = sumA[s][(e-1+M)%M] + A[e];
        }
    }
    
    for (int s=0; s<N; s++) {
        for (int i=0; i<N; i++) {
            int e = (s+i)%N;
            sumB[s][e] = sumB[s][(e-1+N)%N] + B[e];
        }
    }
}

ll solution() {
    ll ret = 0;
    
    calcSum();
    
    mp[0] = 1;
    mp[sumB[0][N-1]]++;             // B 전체 선택
    for (int s=0; s<N; s++) {
        for (int i=0; i<N-1; i++) { // 전체 선택 중복 제거
            int e = (s+i)%N;
            mp[sumB[s][e]]++;
        }
    }
    
    for (int s=0; s<M; s++) {
        for (int i=0; i<M-1; i++) { // 전체 선택 중복 제거
            int e = (s+i)%M;
            ret += mp[P-sumA[s][e]];
        }
    }
    
    ret += mp[P];               // B만 선택하는 경우
    ret += mp[P-sumA[0][M-1]];  // A 전체를 선택하는 경우
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    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];
    
    cout << solution();
    
    return 0;
}