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

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

다른 사람들의 풀이와는 다른 방법으로 풀었지만 일단 해결했기에 게시물을 업로드한다.

처음 봤을 때 이 문제의 특징은 연속된 수의 합을 구하는데 원형이라는 점이다.
이 부분에 대해서 어떻게 해결할까 고민하다가 input 배열의 길이를 2배로 측정해서 그대로 붙여주기로 했다.

그 다음 첫번째 배열에서 가능한 모든 수의 합을 구해준 뒤, map 자료구조에 넣어줬다.
두번째 배열에서 가능한 모든 수의 합을 구하면서 map[p-sum]을 결과 값에 더해주면서 문제를 해결했다.

하지만, 한 피자를 선택 안하는 경우가 있다.

이 경우를 대비해, 처음에 map[0]에 1을 넣어주고, 마지막에 map[p]를 결과 값에 더해줌으로써 한 피자를 선택 안하는 경우를 처리해줬다.

연속된 수의 합을 구하는 과정

연속된 수의 합을 구하는 방식을 for문을 다중으로 사용하는 대신 슬라이딩 윈도우 방식을 응용해서 풀었다.

아직 갈길이 멀다....

#include <iostream>
#include <map>
using namespace std;

int a[2001];
int b[2001];
int m, n, p;
int ret = 0;
map<int, int> sub_sum;

int main() {
	cin >> p >> m >> n;
	for (int i = 0; i < m; i++) {
		int in;
		cin >> in;
		a[i] = in; a[m + i] = in;
	}
	for (int i = 0; i < n; i++) {
		int in;
		cin >> in;
		b[i] = in; b[n + i] = in;
	}
	sub_sum[0] = 1;
	for (int i = 0; i < m; i++) {
		int idx = 0;
		int sum = 0;
		int cnt = 0;
		while (idx <= i) {
			sum += a[idx++];
			cnt++;
		}
		idx = 0;
		while (idx < m) {
			if(sum <= p)
				sub_sum[sum] ++;
			if (i == m - 1)
				break;
			sum -= a[idx];
			sum += a[idx + cnt];
			idx++;
		}
	}

	for (int i = 0; i < n; i++) {
		int idx = 0;
		int sum = 0;
		int cnt = 0;
		while (idx <= i) {
			sum += b[idx++];
			cnt++;
		}
		idx = 0;
		while (idx < n) {
			ret += sub_sum[p - sum];
			if (i == n - 1)
				break;
			sum -= b[idx];
			sum += b[idx+ cnt];
			idx++;
		}
	}
	ret += sub_sum[p];
	cout << ret;
}