[C++] 백준/Gold/10986. 나머지 합

나머지 합 (백준 10986번)

문제 개요

• 문제 설명:
  길이가 $ n $인 수열이 주어지고, 정수 $ m $ 이 주어진다.
  수열의 연속 부분 수열의 합이 $ m $ 으로 나누어 떨어지는 경우의 수를 구하는 문제다.
• 핵심 포인트:
  • 직접 모든 구간의 합을 구하면 시간 복잡도가 $ O(n^2) $ 가 되어 시간 초과 가능성이 높다.
  • 누적 합(presum)과 나머지 연산을 활용하면 효율적으로 $ O(n) $ 내에 해결할 수 있다.

---

접근 방법

1. 누적 합과 나머지 활용

• 누적 합 정의:
  $  S_i = \text{v[0]} + \text{v[1]} + \dots + \text{v[i]} $
  그러면 구간 $ [i, j] $ 의 합은 $ S_j - S_{i-1} $ 이다.
• 나머지 이용:
  구간 합이 $ m $ 으로 나누어 떨어진다는 것은
  $$
  S_j - S_{i-1} \equiv 0 \pmod{m}
  $$
  즉,
  $$
  S_j \equiv S_{i-1} \pmod{m}
  $$
• 두 누적 합의 나머지가 같으면 그 사이 구간의 합은 $ m $ 의 배수임을 의미한다.

2. 구간의 개수 계산

• $ S_i $ 를 $ m $ 으로 나눈 나머지를 $ r $ 라고 할 때,
  동일한 $ r $ 가 여러 번 등장하면 그들 중 두 개를 선택할 때마다 $ m $ 의 배수가 되는 구간이 생긴다.
• 경우의 수는 $ r $ 가 등장한 횟수를 $ k $ 라 하면,
  $$
  \text{경우의 수} = \binom{k}{2} = \frac{k \times (k-1)}{2}
  $$
• 추가로, 누적 합 자체가 0인 경우도 마찬가지로 바로 $ m $으로 나누어 떨어지는 구간으로 직접 센다.

전체 코드

#include <bits/stdc++.h>
using namespace std;

int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m; 
    cin >> n >> m;
    vector<int> v(n);
    unordered_map<int, int> dict;
    long long answer = 0;

    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }

    // 누적 합 계산과 나머지 빈도수 저장
    for (int i = 0, sum = 0; i < n; i++) {
        sum += v[i];
        sum %= m;
        dict[sum]++;
        if (sum == 0) answer++;  // 누적 합 자체가 0인 경우 바로 카운트
    }

    // 동일 나머지를 가진 구간들에 대한 조합으로 경우의 수 추가
    for (const auto& ele : dict) {
        if (ele.second > 1) {
            answer += static_cast<long long>(ele.second - 1) * ele.second / 2;
        }
    }

    cout << answer;
}