백준 2632번 피자 판매

문제 링크입니다: https://www.acmicpc.net/problem/2632

N과 M이 최대 1000이기 때문에 미리 시간복잡도 O(N^2)으로 전처리해도 무방한 문제였습니다.

알고리즘은 아래와 같습니다.

1. 모든 가능한 합을 미리 v와 v2에 전처리 해줍니다.

2. v[i]에 대해 lower_bound와 upper_bound를 이용하여 v2에 (pizza - v[i])가 몇개 있는지 확인하고 결과에 더해줍니다.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int pizza;

        cin >> pizza;

        int M, N;

        cin >> M >> N;

 

        vector<int> A(M), B(N);

        for (int i = 0; i < M; i++)

                 cin >> A[i];

        for (int i = 0; i < N; i++)

                 cin >> B[i];

 

        //전처리

        vector<int> v(1, 0), v2(1, 0);

        int low = 0, high = 0;

        int sum = 0;

        while (low < A.size())

        {

                 sum += A[high++];

                 if (sum <= pizza)

                         v.push_back(sum);

                 else

                 {

                         low++;

                         high = low;

                         sum = 0;

                 }

 

                 //원형 배열

                 if (high == A.size())

                         high = 0;

                 //전체 다 더한 값 중복 방지

                 if ((!low && !high) || high + 1 == low)

                 {

                         low++;

                         high = low;

                         sum = 0;

                 }

        }

 

        low = 0, high = 0, sum = 0;

        while (low < B.size())

        {

                 sum += B[high++];

                 if (sum <= pizza)

                         v2.push_back(sum);

                 else

                 {

                         low++;

                         high = low;

                         sum = 0;

                 }

 

                 //원형 배열

                 if (high == B.size())

                         high = 0;

                 //전체 다 더한 값 중복 방지

                 if ((!low && !high) || high + 1 == low)

                 {

                         low++;

                         high = low;

                         sum = 0;

                 }

        }

 

        sort(v.begin(), v.end());

        sort(v2.begin(), v2.end());

        int result = 0;

        for (int i = 0; i < v.size(); i++)

        {

                 int low = lower_bound(v2.begin(), v2.end(), pizza - v[i]) - v2.begin();

                 int high = upper_bound(v2.begin(), v2.end(), pizza - v[i]) - v2.begin();

                

                 result += high - low;

        }

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~