[백준][이분탐색] 2632 피자판매 c++구현

목차

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

문제

 

문제 구현 방향

연속된 값을 더하는 것이므로 일단 누적합이 생각났다.

경우의 수가 매우 많으므로 각각의 경우를 구한뒤 합치는게 효율적이라고 생각했다.

 

문제 풀이 시 아이디어

 

1. 원형 배열 직선 배열로 만들기

2

2

1

7

2

 

아래와 같이 배열을 한번 더 합치면 원형 배열 구간합 탐색이 가능하다.

2

2

1

7

2

2

2

1

7

2

 

단 시작점이 초기 배열 사이즈-1 인덱스에 오면 탐색을 멈추어야 중복을 막을 수 있다.

사이즈가 초기 배열 사이즈만큼일때는 한번 탐색하고 중단해야한다.

 

 

2. 각 경우 곱해서 구하기

만들어 질 수 있는 각각의 경우를 구해 준 뒤 곱해서 더해준다.

    for (int i = 0; i <= S; i++) {
        total += (resa[i] * resb[S - i]);
    }

 

코드 구현

#include <iostream>
#include <vector>
#include<map>
#include<math.h>
#include <algorithm>

using namespace std;

int S, m, n;
vector<int> a;
vector<int> b;
vector<int> resa(2000000, 0);
vector<int> resb(2000000, 0);
int total = 0;

void Search(int size, vector<int>& v, int identify) {
    int sum = 0;
    int start = 0;
    int end = start + size;
    int capacity;
    if (identify)
        capacity = m;
    else
        capacity = n;

    for (int j = 0; j <= end; j++) {
        sum += v[j];
    }
    if (sum <= S) {
        if (identify)
            resa[sum]++;
        else
            resb[sum]++;
    }

    while ( start < capacity-1) {
        end++;
        sum -= v[start];
        sum += v[end];
        start++;

        if (sum <= S) {
            if (identify)
                resa[sum]++;
            else
                resb[sum]++;
            }
        }
}

void pizza() {
    int asize = 0;
    int bsize = 0;
    for (int i = 0; i < m-1; i++) {
        Search(asize, a, 1);
        asize++;
    }
    for (int i = 0; i < n-1; i++) {
        Search(bsize, b, 0);
        bsize++;
    }

    for (int i = 0; i <= S; i++) {
        total += (resa[i] * resb[S - i]);
    }
  
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int num;
    int sum = 0;
    cin >> S >> m >> n;
    for (int i = 0; i < m; i++) {
        cin >> num;
        a.push_back(num);
        
        sum += num;
    }
    if (sum <= S)
        resa[sum] = 1;
    sum = 0;
    for (int i = 0; i < m; i++) {
        a.push_back(a[i]);
    }
    for (int i = 0; i < n; i++) {
        cin >> num;
        b.push_back(num);
        sum += num;
    }
    if (sum <= S)
        resb[sum] = 1;
    for (int i = 0; i < n; i++) {
        b.push_back(b[i]);
    }
    resa[0] = 1;
    resb[0] = 1;
    pizza();

    cout << total;
   
    return 0;
}