취미로 코딩하기

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

이번에 볼 문제는 백준 28072번 문제인 K512에서 피자 먹기이다.
문제는 아래 링크를 확인하자.

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

psum[i]를 1번부터 i번까지의 피자조각의 무게의 합을 K로 나눈 나머지라 정의하자. 이 배열은 i를 1부터 N까지 차례대로 늘려나가면서 psum[i-1]의 값을 참조해(psum[0]=0으로 정의하자) $O(N)$으로 계산할 수 있다.

L번 조각부터 R번 조각까지로 이루어진 피자 조각을 [L,R]이라 부르자. 이 때, 피자 조각 [L,R]의 무게가 K의 배수라면 psum[L-1]과 psum[R]의 값이 같아야 함을 관찰할 수 있다. 또한, psum[x]와 psum[y]의 값이 같다면 피자 조각 [x+1,y] 및 [y+1,x]의 무게 또한 K의 배수가 됨을 관찰할 수 있다.

위의 관찰을 이용하면 문제의 답은 가능한 k값에 대하여 psum의 값이 k이고 1 이상 N 이하인 i값의 개수의 최댓값이 됨을 알 수 있다. 이를 구하는 코드를 작성해 문제를 해결하자.

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

#include <iostream>
using namespace std;

int N, K;
int arr[1000001];
int cnt[100001];

int ans;

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

	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
		arr[i] += arr[i - 1];
		arr[i] %= K;
		cnt[arr[i]]++;
	}

	for (int i = 0; i < K; i++) ans = max(ans, cnt[i]);

	cout << ans;
}