나머지 합 (feat. 백준, 10986번)

나머지 합
https://www.acmicpc.net/problem/10986

10986번: 나머지 합

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
using namespace std;
long long arr[1000001], dp[1000001], dpp[1001];
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	memset(dpp, 0, sizeof(dpp));
	register int N, M;
	long long ans = 0;
	cin >> N >> M;
	for (register int i = 0; i < N; ++i)
		cin >> arr[i], dp[i] = 0;
	arr[N] = dp[N] = 0;
	for (register int i = N - 1; i >= 0; --i) {
		dp[i] = (dp[i + 1] + arr[i]) % M;
		++dpp[dp[i]];
	}
	for (register int i = 0; i <= M; ++i)
		ans += dpp[i] * (dpp[i] - 1) / 2;
	cout << ans + dpp[0];
	return 0;
}
// *&)*@*

1. 생각보다 굉장히 어려웠습니다.
2. 일반적인 dp 방식으로는 시간 초과가 발생합니다.
3. 구하려는 구간에 대해서 (dp[i] - dp[j]) % M == 0 에 대해서 생각해보면 결국 dp[i] % M == dp[j] % M 인 포인트를 구하면 되는 문제입니다.