[백준] 10986번 : 나머지 합 C++ 문제풀이 솔루션

문제

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

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

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)

둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)

출력

첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.

예제 입력 1

5 3
1 2 3 1 2

예제 출력 1

7

 

(A % C + B % C) % C는 (A + B) % C와 같다. 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값은 동일하다.

 

입력받는 수를 저장하는 sum 벡터를 선언하고, 벡터의 원소를 합 배열로 채운다. 이때 sum[j] % m과 sum[i] % m의 값이 같은 경우, i부터 j까지의 합은 m으로 나누어 떨어진다. 그러므로 벡터의 원소에 대해 % m 연산을 실행하고, 그 중 값이 같은 것들 중 2개를 조합하여 선택하는 경우의 수를 구하면 된다.

sum의 원소가 m으로 나누어 떨어지는 경우는 따로 결과값에 더해주어야한다.

#include <iostream>
#include <vector>
#include <algorithm>
#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false)
using namespace std;

int main() {
  fast_io;
  vector<long> sum;

  int n, m;
  cin >> n >> m;
  vector<long> remain(n, 0);
  long result = 0;
  for (int i = 0; i < n; i++) {
	int num;
	cin >> num;
	if (i != 0)sum.push_back((num + sum[i - 1]) % m);
	else sum.push_back(num % m);
	if (sum[i] == 0) result++;
  }

  for (int i = 0; i < n; i++) {
	remain[sum[i]]++;
  }
  for (int i = 0; i < remain.size(); i++) {
	remain[i] = remain[i] * (remain[i] - 1);
	result += remain[i] / 2;
  }
  cout << result;
  return 0;
}