[백준][C++] 2632번: 피자판매 (256)

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

 

2632번: 피자판매

 

1. 생각의 흐름

연속된 부분합의 수를 잘 구해야 하는 문제이다.

 

우선 input 범위가 1000 까지라고 명시되어있으니, 그냥 O(n^2) 방식으로 2중 for문 돌면서 구하는 방식으로 합을 구하면 된다.

(ps O(n^2) 알고리즘은 input이 1만까지 안정권 이라 알고있다)

 

우선 문제에서 주어진 예시를 생각해 보자.

7
5 3
2
2
1
7
2
6
8
3

 

합으로 7을 만들어야 하며, vec1(2, 2, 1, 7, 2) 와 vec2(6, 8, 3) 으로 피자가 나뉘어 져 있는 상황이다.

 

우선 vec1에서 합으로 나올 수 있는 모든 가능한 경우를 count 해야 한다.

총 원소의 수는 5개이니 최대 4개까지 만 사용하여 가능한 경우의 수를 count 한 후, 마지막에 원소 5개를 모두 사용하는 경우는 한번만 추가해 준다.

 

우선 원소 1개, 2개, 3개, 4개를 사용하여 나올 수 있는 합의 경우의 수를 구하는 코드는 다음과 같다.

이때 원소 5개 까지 한번에 구하려 하면 5개를 이용한 경우가 5번 중복된다.

(2, 2, 1, 7, 2)

(2, 2, 2, 1, 7)

(7, 2, 2, 2, 1)

(1, 7, 2, 2, 2)

(2, 1, 7, 2, 2) 모두 똑같은 14를 합으로 반환하는 경우이다. 중복 카운트 하면 안된다!

vector<int> sum1;
for(int i = 0; i < n; i++){
    int sum = 0;
    for(int j = i; j < i+n-1; j++){
        sum += vec1[j%n];
        sum1.push_back(sum);
    }
}

 

이후 5개의 원소를 이용하는 경우를 추가해 준다.

int sum = 0; // 전체 합을 구하는 경우 중복을 막기위해 1번만 추가해줌
for(int j = 0; j < n; j++){
    sum += vec1[j];
}
sum1.push_back(sum);

 

그 다음부터는 투포인터 알고리즘을 이용하여 합으로 우리가 원하는 7이 나오는 경우의 수를 모두 count 해주면 된다.

다만 투포인트 알고리즘으로 sum1, sum2 에서 각각 하나씩 고르는 경우의 수를 구한후, 각 sum1에서만 구하는 경우, sum2에서만 구하는 경우의 수 또한 더해주어야 답이 나온다.

투포인터는 구하는 방식은 다음과 같다!

 

▶ upper_case를 활용한 투포인트 알고리즘

원래는 그냥 투포인터 알고리즘을 구현하여 해결했는데, 다른 분들의 풀이를 보니 upper_case를 활용하여 더욱 간단하게 해결하시길래 나도 사용해 봤다.

long long res(0);
for(int i = 0; i < front.size(); i++){
    int low = lower_bound(end.begin(), end.end(), T - front[i]) - end.begin();
    int high = upper_bound(end.begin(), end.end(), T - front[i]) - end.begin();
    res += high - low;
}

 

우리가 구하려고 하는 값 T에서 front[i]를 뺀 값을 end에서 찾으면 된다. 이때 중복되어 있을 수 있으니 lower_bound - upper_bound를 이용하면 개수를 구할 수 있다!

 

나의 코드

#include <bits/stdc++.h>

using namespace std;

int p;
int m, n;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> p;
    cin >> m >> n;

    vector<int> pizzaA(m), pizzaB(n);
    for(int i = 0; i < m; i++) {
        cin >> pizzaA[i];
    }

    for(int i = 0; i < n; i++) {
        cin >> pizzaB[i];
    }

    vector<int> sum1(1, 0);
    for(int i = 0; i < m; i++) {
        int sum = 0;
        for(int j = i; j < i + m - 1; j++) {
            sum += pizzaA[j % m];
            sum1.push_back(sum);
        }
    }
    sum1.push_back(accumulate(pizzaA.begin(), pizzaA.end(), 0));

    vector<int> sum2(1, 0);
    for(int i = 0; i < n; i++) {
        int sum = 0;
        for(int j = i; j < i + n - 1; j++) {
            sum += pizzaB[j % n];
            sum2.push_back(sum);
        }
    }
    sum2.push_back(accumulate(pizzaB.begin(), pizzaB.end(), 0));

    sort(sum1.begin(), sum1.end());
    sort(sum2.begin(), sum2.end());
    int res = 0;
    for (int i = 0; i < sum1.size(); i++) {
        int value = p - sum1[i];
        if(value < 0) {
            break;
        }
        int low = lower_bound(sum2.begin(), sum2.end(), value) - sum2.begin();
        int high = upper_bound(sum2.begin(), sum2.end(), value) - sum2.begin();
        res += high - low;
    }

    cout << res;

    return 0;
}