취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2632번 문제인 피자판매이다.
문제는 아래 링크를 확인하자.

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

$N$조각으로 나뉘어진 피자에서 판매할 수 있는 모양은 $O(N^2)$가지뿐임을 관찰하자. 따라서 각 피자에서 얻을 수 있는 모든 경우에 제한시간 내에 충분히 접근해 볼 수 있다. 이해가 되지 않는다면, 구간 $[L,R]$의 개수를 생각해보자. 그리고 각 구간을 시계방향으로 $L$번 조각부터 $R$번 조각까지의 모임과 대응시켜보자. (단, 피자 전체를 한 조각으로 생각하는 경우에 유의하자. 또한 피자를 판매하지 않는 경우도 구현에 따라 고려해야 함에 유의하자.)

주어진 조건에 따라 한 피자에서 얻을 수 있는 피자 조각의 넓이는 100만 이하이므로, 합이 손님이 원하는 피자의 크기가 되게끔 두 피자에서 피자를 고르는 경우를 모두 찾아 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int N, M, K;
int A[2001], B[2001];
int X[2000001], Y[2000001];
ll ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> K >> N >> M;
	for (int i = 1; i <= N; i++) cin >> A[i];
	for (int i = 1; i <= N; i++) A[i + N] = A[i];
	for (int i = 1; i <= N * 2; i++) A[i] += A[i - 1];
	for (int L = 0; L < N; L++) {
		for (int k = 1; k < N; k++) {
			X[A[L + k] - A[L]]++;
		}
	}
	X[0]++, X[A[N]]++;

	for (int i = 1; i <= M; i++) cin >> B[i];
	for (int i = 1; i <= M; i++) B[i + M] = B[i];
	for (int i = 1; i <= M * 2; i++) B[i] += B[i - 1];
	for (int L = 0; L < M; L++) {
		for (int k = 1; k < M; k++) {
			Y[B[L + k] - B[L]]++;
		}
	}
	Y[0]++, Y[B[M]]++;

	for (int i = 0; i <= K; i++) {
		ans += (ll)X[i] * Y[K - i];
	}

	cout << ans;
}