백준 10986번 나머지 합

문제

수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.

즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

문제풀이

사용한 알고리즘: 수학

(1) 생각

 연속합이 modulo M 에서 0인 구간을 찾는 문제입니다.
 (A_1 ~ A_x 의 연속합)%M 을 map으로 종류별 개수로 모두 저장합니다.
 : map< 연속합%M , 개수 >
 A_1~A_a = t , A_1~A_b = t 로 같다면, A_a~A_b 의 연속합은 0임을 생각할 수 있습니다.

(2) 코드 14~22

 [연속합%M] 의 개수들을 저장해줍니다.
 이때 연속합%M=0 이면 그 구간 자체로 정답이 되는걸 생각해줍니다.

(3) 코드 23~26

 조합(combination) 을 생각해주면 됩니다.
 과정(1) 에서 언급한 것 처럼 연속합%M의 값이 같은 구간 2개를 고르는 경우수를 구합니다.
 연속합%M 의 개수가 X 라면, 그 개수는 X C 2 = X * (X-1) /2 입니다.

	#include <bits/stdc++.h>
	using namespace std;
	// 꾸준함님 블로그 참고
	typedef long long ll;
	int N, M;
	ll pSum[1111111];
	map<ll, ll> cnt;
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> M;
	ll ans = 0LL;
	for (int i = 1; i <= N; ++i){
	int a;
	cin >> a;
	pSum[i] = (pSum[i-1]+a)%M;
	// 0 이면 바로 정답~
	if(pSum[i]==0) ans++;
	// 개수체크
	cnt[pSum[i]]++;
	}
	// M C 2
	// 예를들어 1~4 , 1~8 구간이 둘다 mod M 에서 나머지 2 이면 4~8 구간이 mod M 에서 0
	for(auto it: cnt)
	ans += (it.second*(it.second-1)) / 2;
	cout << ans << '\n';
	return 0;
	}

view raw BOJ 10986.cpp hosted with ❤ by GitHub