[백준 10986] 나머지 합 구하기

나머지 합 구하기 [C++]

문제 링크: https://www.acmicpc.net/problem/10986

난이도: 🟡🟡🟡

문제 설명

문제 접근

1. N의 범위가 10^6까지기 때문에 구간합을 이용한다.
2. 합배열 S의 모든 구간을 M으로 나누었을 때 나머지가 0이라면 그 구간은 나누어 떨어진다는 뜻이다.
   ex) M = 3, S[0] = 3, S[1] = 5, S[2] = 9일 때 S[0]과 S[2]는 3으로 나누어 떨어진다.
3. S의 모든 구간을 M으로 나누었을 때 나머지가 같은 구간의 합은 M으로 나누어 떨어진다.
   ex) M = 3, S[0] = 2, S[1] = 5일 때 S[1] % 3 - S[0] % 3 = 0
즉, 이 구간은 나누어 떨어진다는 뜻이다.
4. 2번과 3번을 구한 것이 정답.
   
   

제출 코드

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

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;
    
	long cnt = 0;
	vector<long> s(N, 0);
	vector<long> c(M, 0);

	// 첫 번째 값 == 첫 번째 합배열의 값
	cin >> s[0];

	int temp; 
	for (int i = 1; i < N; i++) 
	{
		cin >> temp;
		s[i] = s[i - 1] + temp;
	}
	int new_s;
	for(int i = 0; i < N; i++)
	{
		new_s = s[i] % M;
		if (new_s == 0)
			cnt++;
		c[new_s]++;
	}
	for (int i = 0; i < M; i++)
	{
		if (c[i] > 1)
			cnt += (c[i] * (c[i] - 1) / 2);
	}
	cout << cnt;
	
	return 0;
}

결과