이번에는 백준 2632번 피자판매 문제를 풀어보았습니다.
이 문제는 A 피자와 B 피자에서 각각 연속된 조각들을 선택하여 만들 수 있는 모든 크기를 구한 뒤, 두 피자의 합이 주문한 크기가 되는 경우의 수를 계산하는 문제입니다.
피자는 원형으로 이어져 있기 때문에 % 연산을 사용하여 연속된 조각의 합을 계산하였습니다.
문제 설명
A 피자와 B 피자는 각각 여러 개의 조각으로 나누어져 있습니다.
손님이 원하는 피자의 크기가 주어졌을 때 다음 세 가지 방식으로 판매할 수 있습니다.
- A 피자만 사용
- B 피자만 사용
- A 피자와 B 피자를 같이 사용
단, 하나의 피자에서 2조각 이상을 선택한다면 반드시 연속된 조각이어야 합니다.
또한 피자는 원형으로 이어져 있기 때문에 마지막 조각 다음에는 다시 첫 번째 조각이 이어집니다.
손님이 원하는 크기를 만들 수 있는 모든 경우의 수를 구하는 문제입니다.
풀이 아이디어
먼저 A 피자에서 만들 수 있는 모든 연속 부분합을 구합니다.
각 합이 몇 번 만들어지는지를
pizza_a_sum[합]에 저장하였습니다.
B 피자도 같은 방식으로
pizza_b_sum[합]에 경우의 수를 저장하였습니다.
이후 주문한 크기가 tar일 때,
A에서 i
B에서 tar - i를 선택하면 전체 크기가 tar가 됩니다.
따라서
pizza_a_sum[i] * pizza_b_sum[tar-i]를 모두 더하면 정답을 구할 수 있습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tar, ret=0;
int m,n;
vector<int> pizza_a;
vector<int> pizza_b;
cin >> tar >> m >> n;
vector<int> pizza_a_sum(tar+1,0);
vector<int> pizza_b_sum(tar+1,0);
for (int i=0; i<m; i++) {
int temp;
cin >> temp;
pizza_a.push_back(temp);
}
for (int i=0; i<n; i++) {
int temp;
cin >> temp;
pizza_b.push_back(temp);
}
pizza_a_sum[0] = 1;
pizza_b_sum[0] = 1;
for (int i=0; i<m; i++) {
int tmp_sum = 0;
for (int j=0; j<m-1; j++) {
tmp_sum += pizza_a[(i+j)%m];
if (tmp_sum > tar) break;
pizza_a_sum[tmp_sum]++;
}
}
int total_a_sum = 0;
for (int i=0; i<m; i++) {
total_a_sum += pizza_a[i];
}
if (total_a_sum <= tar) pizza_a_sum[total_a_sum]++;
for (int i=0; i<n; i++) {
int tmp_sum = 0;
for (int j=0; j<n-1; j++) {
tmp_sum += pizza_b[(i+j)%n];
if (tmp_sum > tar) break;
pizza_b_sum[tmp_sum]++;
}
}
int total_b_sum = 0;
for (int i=0; i<n; i++) {
total_b_sum += pizza_b[i];
}
if (total_b_sum <= tar) pizza_b_sum[total_b_sum]++;
for (int i=0; i<=tar; i++) {
ret += ( pizza_a_sum[i] * pizza_b_sum[tar-i] );
}
cout << ret;
return 0;
}풀이 흐름
-
주문한 피자의 크기와 A, B 피자의 조각 개수를 입력받습니다.
-
A 피자와 B 피자의 각 조각 크기를 저장합니다.
-
아무 조각도 선택하지 않는 경우를 위해 합이 0인 경우의 수를 1로 설정합니다.
-
A 피자의 모든 시작 위치에서 연속된 조각의 합을 구합니다.
-
각 합이 몇 번 만들어지는지를
pizza_a_sum에 저장합니다. -
A 피자 전체를 선택하는 경우는 별도로 한 번 추가합니다.
-
B 피자도 같은 방식으로 모든 연속 부분합의 경우의 수를 구합니다.
-
i + (tar - i) = tar를 만족하도록 A와 B의 경우의 수를 곱합니다. -
모든
i에 대해 경우의 수를 더한 뒤 출력합니다.
구현 포인트
1. 합마다 경우의 수 저장
vector<int> pizza_a_sum(tar+1,0);
vector<int> pizza_b_sum(tar+1,0);각 배열의 인덱스는 만들 수 있는 피자의 크기를 의미합니다.
예를 들어
pizza_a_sum[7] = 3이라면 A 피자에서 연속된 조각을 선택하여 크기 7을 만드는 방법이 3개 있다는 뜻입니다.
2. 피자를 하나도 선택하지 않는 경우
pizza_a_sum[0] = 1;
pizza_b_sum[0] = 1;A 피자만 사용하거나 B 피자만 사용하는 경우도 고려해야 합니다.
예를 들어 주문 크기가 10이고 A 피자에서 크기 10을 만들 수 있다면
A = 10
B = 0으로 생각할 수 있습니다.
따라서 아무 조각도 선택하지 않는 경우를 하나의 경우로 두었습니다.
3. 원형 피자 처리
피자는 마지막 조각과 첫 번째 조각이 이어져 있습니다.
따라서 다음과 같이 % 연산을 사용하였습니다.
tmp_sum += pizza_a[(i+j)%m];예를 들어 조각이 5개이고 시작점이 4번이라면
4 → 0 → 1 → 2 ...순서로 이어서 탐색할 수 있습니다.
이를 통해 배열을 실제로 두 번 이어 붙이지 않고 원형 구조를 구현하였습니다.
4. 모든 시작 위치에서 연속합 계산
for (int i=0; i<m; i++) {
int tmp_sum = 0;
for (int j=0; j<m-1; j++) {i를 시작 위치로 두고 연속된 조각의 합을 구합니다.
각 시작점마다 최대 m-1개의 조각까지만 더합니다.
tmp_sum += pizza_a[(i+j)%m];만들어진 합이 주문 크기 이하라면 해당 경우의 수를 증가시킵니다.
pizza_a_sum[tmp_sum]++;5. 전체 피자를 따로 처리하는 이유
for (int j=0; j<m-1; j++)에서는 최대 m-1개의 조각까지만 선택합니다.
전체 m개의 조각을 선택하는 경우까지 각 시작점에서 계산하면, 시작 위치만 다를 뿐 실제로는 같은 피자 한 판 전체를 여러 번 세게 됩니다.
예를 들어 A 피자가 4조각이라면
0부터 4조각
1부터 4조각
2부터 4조각
3부터 4조각은 모두 같은 피자 전체를 선택한 경우입니다.
따라서 전체 피자를 선택하는 경우는 따로 한 번만 추가하였습니다.
int total_a_sum = 0;
for (int i=0; i<m; i++) {
total_a_sum += pizza_a[i];
}
if (total_a_sum <= tar)
pizza_a_sum[total_a_sum]++;B 피자도 같은 방식으로 처리합니다.
6. 주문 크기를 넘어가면 중단
if (tmp_sum > tar) break;모든 피자 조각의 크기는 양수입니다.
따라서 현재 연속합이 이미 주문 크기보다 커졌다면 조각을 더 추가해도 값은 계속 증가합니다.
즉, 이후에는 절대로 주문 크기를 만드는 데 사용할 수 없습니다.
따라서 해당 시작 위치에서는 더 이상 계산하지 않고 반복문을 종료하였습니다.
7. A와 B의 경우의 수 합치기
A에서 크기 i를 만들고 B에서 크기 tar-i를 만들면 전체 크기는 정확히 tar가 됩니다.
for (int i=0; i<=tar; i++) {
ret += pizza_a_sum[i] * pizza_b_sum[tar-i];
}예를 들어
pizza_a_sum[3] = 2
pizza_b_sum[4] = 3이고 주문 크기가 7이라면
A에서 3을 만드는 방법 2개
×
B에서 4를 만드는 방법 3개이므로 총 6가지 방법이 만들어집니다.
따라서 두 경우의 수를 곱해서 정답에 더합니다.
8. 한 종류의 피자만 사용하는 경우도 포함
앞에서
pizza_a_sum[0] = 1;
pizza_b_sum[0] = 1;로 설정했기 때문에 별도의 조건 없이 한 종류의 피자만 사용하는 경우도 자동으로 계산됩니다.
예를 들어 A 피자만 사용해서 주문 크기를 만드는 경우는
pizza_a_sum[tar] * pizza_b_sum[0]으로 계산됩니다.
반대로 B 피자만 사용하는 경우는
pizza_a_sum[0] * pizza_b_sum[tar]으로 계산됩니다.
9. 원형 연속 부분합 문제
일반적인 배열에서는 연속 부분합을 구할 때 마지막 인덱스를 넘어갈 수 없습니다.
하지만 이 문제의 피자는 원형이므로 마지막 조각에서 첫 번째 조각으로 이어지는 경우도 확인해야 합니다.
이를
(i+j)%m형태로 처리하였습니다.
따라서 이 문제는 원형 배열에서 가능한 연속 부분합의 개수를 구한 뒤 두 종류의 경우의 수를 합치는 문제라고 볼 수 있습니다.
시간복잡도
A 피자는 모든 시작점 m개에서 최대 m-1개의 조각을 확인합니다.
따라서
O(m²)의 시간이 필요합니다.
B 피자도 마찬가지로
O(n²)이 필요합니다.
마지막으로 0부터 tar까지 순회하므로
O(tar)가 추가됩니다.
따라서 전체 시간복잡도는
O(m² + n² + tar)입니다.
m, n은 최대 1000이고 tar는 최대 2,000,000이므로 충분히 해결할 수 있습니다.
