[BOJ] 백준 10986 나머지 합

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

 Input 

5 3

1 2 3 1 2

 

 Output 

7

부분합 psum을 이용해서 특정 구간합을 비교적 빠르게 구할 수 있지만,

이 문제의 경우 그렇게 하더라도 M으로 나누어 떨어지는 구간을 확인하기에는 TLE 발생

#include <stdio.h>
 
typedef long long LL;
const int MAX_N = 1e6;
LL psum[MAX_N + 10];
int ans;
int main(void) {
    // freopen("input.txt", "r", stdin);
    int N, M, num;
    scanf("%d %d", &N, &M);
    
    for (int i = 1; i <= N; ++i) {
        scanf("%d", &num);
        psum[i] = psum[i - 1] + num;
    }
 
    for (int i = 1; i < N; ++i) {
        for (int j = i; j <= N; ++j) {
            if ((psum[j] - psum[i - 1]) % M == 0)
                ans++;
        }
    }
 
    printf("%d\n", ans);
}

 

구현

① 먼저 psum[]에 저장할 때, %M 처리한 결과를 저장합니다.

각각의 나머지들이 나타난 횟수를 cnt[] 배열에 저장합니다.

M = 3일 때, cnt[] = [3, 2, 0]

② psum[i] % M == 0인 곳은 [1, i]까지의 구간합 M으로 나누어 떨어지는 지점에 해당됩니다.

③ psum[A] % M의 결과가 x일 때, 또 다른 곳 psum[B] % M에서 같은 결과 x가 나온다면 

    [A+1, B] 구간 합도 M으로 나누어 떨어집니다.

    즉, [1, A] 구간 합의 나머지와 [1, B] 구간합의 나머지가 동일한 경우 [A+1, B] 구간합은 M으로 나누어 떨어집니다.

    ex) psum[1] = psum[4] = 1 → [2, 4]의 구간합 = 2 + 3 + 1 = 6 → 6 % M = 0

    즉, psum[] % M에서 동일한 결과 나온 값들에 대해서 2가지를 선택하는 경우입니다. → cnt[i]C2

    ex) 『0』 이 3번 나타난 경우 =  3C2 

          ( 다른 수와 달리 『0』의 경우는 앞서 설명한거와 같이 단독으로도 M으로 나누어 떨어집니다.)

---

#include <stdio.h>
#include <stdlib.h>
 
typedef long long LL;
const int MAX_N = 1e6;
const int MAX_M = 1e3;
LL psum[MAX_N + 10], cnt[MAX_M + 10], ans;
 
int main(void) {
    // freopen("input.txt", "r", stdin);
    int N, M, num;
    scanf("%d %d", &N, &M);
    
    for (int i = 1; i <= N; ++i) {
        scanf("%d", &num);
        psum[i] = (psum[i - 1] + num) % M;
        cnt[psum[i]]++;
    }
 
    ans = cnt[0];
    for (int i = 0; i < M; ++i) {
        ans += (cnt[i] * (cnt[i] - 1)) / 2;
    }
 
    printf("%lld\n", ans);
}