[C++] 백준(BOJ) - 2632 : 피자판매
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
고객이 두 종류의 피자 A와 B를 취급하는 피자가게에서 피자를 주문하고자 한다. <그림 1>과 같이 각 종류의 피자는 다양한 크기의 여러 개의 피자조각으로 나누어져 있다. 각 조각에 쓰여진 숫자는 피자조각의 크기를 나타낸다.
고객이 원하는 피자의 크기를 이야기하면, 피자가게에서는 한 종류의 피자를 2 조각 이상 판매할 때는 반드시 연속된 조각들을 잘라서 판매한다. 이때 판매한 피자조각의 크기 합이 주문한 크기가 되어야 한다. 판매한 피자조각은 모두 A종류이거나, 모두 B종류이거나, 또는 A와 B 종류가 혼합될 수 있다. 예를 들어서, <그림 1> 과 같이 잘라진 피자가 있을 때, 손님이 전체 크기가 7 인 피자를 주문하면, 피자 가게에서는 <그림2>와 같이 5 가지 방법으로 피자를 판매할 수 있다.
피자가게에서 손님이 원하는 크기의 피자를 판매하는 모든 방법의 가지 수를 계산하는 프로그램을 작성하시오
입력
첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n ≤ 1000). 세 번째 줄부터 차례로 m 개의 줄에는 피자 A의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다. 그 다음 n 개의 줄에는 차례로 피자B의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다. 각 종류의 피자조각의 크기는 시계방향으로 차례로 주어지며, 각 피자 조각의 크기는 1000 이하의 자연수이다.
출력
첫째 줄에는 피자를 판매하는 방법의 가지 수를 나타내는 정수를 출력한다. 피자를 판매하는 방법이 없는 경우에는 숫자 0을 출력한다.
알고리즘
- 누적합
풀이
- 배열
- 시간/공간복잡도 면에서 비효율
- 경우의 수
- 모든 합 구해서 저장하기보다 횟수만 저장하는 방식이 효율적
- map 자료구조 / counting
- 원형자료구조
- 선형자료구조를 두개로 이어붙여서 선형자료구조로 구현 가능
- 구간 쿼리
- 누적합
psum[i] = psum[i-1] + a[i];psum[i] - psum[i-k]를 통해 경우의 수 모두 체크 가능
코드
// BOJ-2632 : 피자판매
#include <bits/stdc++.h>
using namespace std;
int k, n, m, res;
int a[1004], b[1004], psum_a[2008], psum_b[2008];
map<int, int> aCnt, bCnt; // a, b 배열 누적합 경우의 수를 카운팅한 맵
void make(int n, int psum[], map<int, int>& mp)
{
for (int interval = 1; interval <= n; interval++)
{
for (int start = interval; start <= n + interval - 1; start++)
{
int sum = psum[start] - psum[start - interval];
mp[sum]++;
if (interval == n) break;
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> k >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
psum_a[i] = psum_a[i - 1] + a[i];
}
for (int i = n + 1; i <= n * 2; i++) psum_a[i] = psum_a[i - 1] + a[i - n];
for (int i = 1; i <= m; i++)
{
cin >> b[i];
psum_b[i] = psum_b[i - 1] + b[i];
}
for (int i = m + 1; i <= m * 2; i++) psum_b[i] = psum_b[i - 1] + b[i - m];
make(n, psum_a, aCnt);
make(m, psum_b, bCnt);
res = (aCnt[k] + bCnt[k]); // a와 b 혼자서 k를 만드는 각각의 경우
for (int i = 1; i < k; i++)
{
res += (aCnt[i] * bCnt[k - i]); // a와 b의 합이 k가 되는 경우
}
cout << res << '\n';
return 0;
}
평가
- 모든 합을 구해서 저장해야 하는 경우가 아닌 경우에 횟수만 필요할 때는 그것만 빼서 저장해서 사용한다
- 원형자료구조는 (선형자료구조 * 2)로 변경할 수 있다
- 구간쿼리를 구하는 문제는 누적합으로 문제 해결 가능
