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

문제 링크

https://www.acmicpc.net/problem/10986

풀이

• 2중 배열을 사용하면, 시간복잡도가 O(n^2)로 시간초과
  • 모듈러 연산을 먼저 이해할 필요가 있음

1. 누적합의 나머지 구하기

• 모듈러 연산 공식

  ((A%M)+(B%M)) % M = (A+B) % M

• 공식을 사용해 특정 구간의 나머지는 아래와 같은 식으로 구할 수 있음
  • i~j 구간의 나머지

    ((sum(j)%M) - (sum(i)%M)) % M = (sum(j) - sum(i)) % M

• 우리는 나누어 떨어지는 부분을 구하면 됨

  ((sum(j)%M) - (sum(i)%M)) % M = 0

  즉, ((sum(i)%M) = (sum(j)%M))

0 ~ i, j까지의 누적합 나머지가 같다면 i~j 는 0으로 나누어 짐

2. 연속 부분 구간의 개수 구하기

• 나머지가 같은 것들이 n개가 있을 경우
  • n개 중 2개를 고르는 조합으로 생각할 수 있음
    → nC2 = (n*(n-1))/2
• 처음부터 특정 위치까지의 합이 M으로 딱 나누어떨어지는 경우
  - 나머지가 0인 개수를 더해주면 됨

조합 공식

• 즉, 우리는 같은 나머지를 가지는 누적 합 중에서 2개를 뽑으면 됨
  • (arr[i] * (arr[i] - 1)) / 2

코드

#include <iostream>

using namespace std;

int main(){
    // C++ 입출력 최적화
    ios::sync_with_stdio(false);  
    // cin 실행 후 cout 자동 flush 방지
    cin.tie(NULL);  

    int n,m;
    cin >> n >> m;

    // 나머지 배열 초기화
    long long arr[m] = {0}; 
    for (int i=0; i<m; i++) {
        arr[i]=0;
    }

    long long sum = 0;
    for (int i=0; i<n; i++) {
        int x;
        cin >> x;
        sum += x;

        arr[sum%m]++;    
    }

    // 나머지가 0인 경우는 독립적으로도 count 가능
    long long cnt = arr[0];
    for (int i=0; i<m; i++) {
        if(arr[i]!=0) cnt += (arr[i] * (arr[i] - 1)) / 2;
    }

    cout << cnt;
    return 0;
}

조합 공식도 다시 찾아보고, 모듈러 성질도 다시 복습하면서 푼 문제.
세상엔 정말 똑똑한 사람이 많다…