[C++] 10986번 나머지 합 - 수학, 누적 합

1. 문제

• 수열 \(A_{i}\)가 주어진다. 연속된 부분 구간의 합이 M으로 나눠지는 구간의 개수를 구하여라

<입력>

• - 1 -   \(N, M(1 \leq N 10^{6}, 2 \leq M \leq 10^{3})\)
• - 2 -   \(A_{i}(0 \leq A_{i} \leq 10^{9})\)

<출력>

• 연속된 부분 구간의 합이 M으로 나눠 떨어지는 구간의 개수를 출력한다.

2. 재정의

• \(A_{i} + ... + A_{j} (i \leq j)\)의 합이 M으로 나누어 떨어지는 \((i, j)\)쌍의 개수 출력

3. 해결 방법

• 두 구간의 나머지가 M으로 같다면 두 구간의 합의 차의 나머지는 0이다. 즉 이를 이용해 누적합의 차가 k가 되는 구간(0, i)의 개수를 remain[k]에 저장하고 나서 kC2와 remain[0]을 더해주면 된다.

4. 실수한 점, 개선할 점

• int 범위를 벗어날 수 있으므로 조심한다. (S, A, cnt모두 ing 범위를 초과할 수 있다.)

 

<코드>

#include <iostream>

using namespace std;
typedef long long ll;

const int MAX_M = 1001;

// <문제>
// 수열의 크기 N, 나누는 값 M
int N, M;

// <누적합>
// 수열 A, 누적합 S
ll A, S;
// 나머지가 i인 누적합의 개수 remainder[i]
ll remain[MAX_M];

// (i, j)쌍의 개수
ll cnt;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> N >> M;
    for(int i=1; i<=N; i++) {
        cin >> A;
        // 누적합 구하기
        S = (S + A) % M;
        remain[S]++;
    }
    
    cnt += remain[0];
    for(int i=0; i<M; i++)
        cnt += remain[i]*(remain[i]-1)/2;
    
    cout << cnt;
    
    return 0;
}

 

<누적 합>

https://jow1025.tistory.com/47

누적합(prefix sum)

 

<문제 바로가기>

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

10986번: 나머지 합

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.