[BOJ] #2632 피자판매

시간 제한	메모리 제한	정답 비율
2 초	128 MB	36.331 %

2632번: 피자판매

 

문제

해결

key point, 원형, 누적합, 부분합, 완전탐색

1.  

   배열 크기 유의하기. 처음에 배열을 작게 잡아서 계속 시간초과가 났었다. → 5번 줄

2. 피자가 원형이기 때문에 `왼→오` 방향으로 누적합을 구하고, `오→왼` 방향으로도 누적합을 구한다. → 13, 19번 줄

3. 부분 합을 구할 때는 j를 `i + n - 1` 이전까지 반복한다. → 23, 38번 줄

   1. 실제 sumA, sumB 배열은 n * 2, m * 2 크기이기 때문에 n개 씩만 확인하고

   2. 부등호가 <= 가 아닌 < 인 이유는 포함하여 i + n - 1까지 확인하면 그 값은 sumA[n]이 되고, i가 n까지 반복되는동안 sumA[n]이 계속해서 배열에 추가되는 문제가 발생한다.

4. 부분합을 다 구했다면 마지막에 전체 총합 sumA[n], sumB[m]을 a, b배열에 추가한다. → 33 번 줄

   1. 3번에서 sumA[n], sumB[m] 을 제외한 부분합을 구했기 때문에 마지막에 추가한다.

5. A, B중 한 종류만 사용하여 피자를 판매할 수 있게 각각 공집합 0을 a, b, 배열에 추가한다.

6. 가능한 개수를 헤아려 경우의 수를 구한다. → 37번 for문.

   1. 이 부분은 많은 방법으로 풀 수 있는데 이번에는 0조각부터 S 조각까지 A피자와 B피자로 만들 수 있는지 확인했다.

 

 

 

 

코드

메모리	시간
13552 KB	180 ms

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int sumA[3010], sumB[3010], ans; // 누적합
int main() {
    int s, n, m;
    scanf("%d%d%d", &s, &n, &m);
    for (int i = 1, a; i <= n; i++) {
        scanf("%d", &a);
        sumA[i] = sumA[i - 1] + a;
    }
    for (int i = n + 1; i <= n * 2; i++) // n -> 1 -> 2 -> 3 ... 누적합구해줌
        sumA[i] = sumA[i - n] + sumA[n];
    for (int i = 1, b; i <= m; i++) {
        scanf("%d", &b);
        sumB[i] = sumB[i - 1] + b;
    }
    for (int i = m + 1; i <= m * 2; i++) // n -> 1 -> 2 -> 3 ... 누적합구해줌
        sumB[i] = sumB[i - m] + sumB[m];
 
    vector<int> a, b; // 나올수 있는 부분 합 - 누적합 활용
    for (int i = 1; i <= n; i++) {
        for (int j = i; j < i + n - 1; j++) {
            a.push_back(sumA[j] - sumA[i - 1]);
        }
    }
    for (int i = 1; i <= m; i++) {
        for (int j = i; j < i + m - 1; j++) {
            b.push_back(sumB[j] - sumB[i - 1]);
        }
    }
    a.push_back(sumA[n]); b.push_back(sumB[m]);
    a.push_back(0); b.push_back(0);
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    for (int i = 0; i <= s; i++) {
        auto p1 = equal_range(a.begin(), a.end(), i);
        auto p2 = equal_range(b.begin(), b.end(), s - i);
        ans += (p1.second - p1.first) * (p2.second - p2.first);
    }
    printf("%d", ans);
    return 0;
}