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

안녕하세요 오늘은 아침부터 예비군 통지서가 온 덕에 입꼬리가 내려가는 하루네요^^ 하하

단순 누적합 문제처럼 보이지만 고려할 부분이 많은 문제가 있어 하나 소개해드릴까 합니다. 그럼 시작해보죠!!

 

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

10986번: 나머지 합

 

1. 문제

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

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

 (1 ≤ N ≤ 10^6, 2 ≤ M ≤ 10^3, 0 ≤ Ai ≤ 10^9)

 

2. 풀이

구간합이 M으로 나누어 떨어지는 경우의 수를 구하는 문제입니다.

가장 그리디한 풀이는 sum[i][j]라는 배열을 선언하고 모든 구간합을 구한 후 sum[i][j] % M = 0이 되는 경우의 수를 구하는 것일텐데요

골드 3 문제답게 10^6이라는 통 큰 N을 주면서 O(n^2)의 시간복잡도를 방지하였습니다.(prefix sum으로 1차원 배열을 하더라도 시간복잡도는 똑같겠네요).

핵심은 '모듈러 연산'이 0이 되는 경우의 수를 구하는 것입니다.

일단 prefix sum으로 sumarr[j] - sumarr[i-1]이 구간합이 되게끔 누적합을 모두 구해줍니다.

우리가 궁금한 것은 (sumarr[j] - sumarr[i-1]) % M = 0 이 되는 것인데

 

모듈러 연산은

(A + B) % C = (A % C + B % C) % C

(A - B) % C = (A % C - B % C) % C

가 성립합니다

 

따라서 (sumarr[j] - sumarr[i-1]) % M = 0 인 경우라면

(sumarr[j] % M - sum[i-1] % M) % M = 0이 될 것이고

저희는 sumarr[j] % M = sum[i-1] % M 인 경우의 수를 찾으면 되는 것입니다.

 

추가로 sumarr[j] % M = sum[i-1] % M 인 경우의 수는 서로 다른 두 누적합의 나머지가 같은 경우만 고려한 것이고

Ai 원소 하나로 M으로 나누어 떨어지는 경우의 수도 있으니 이 또한 추가로 더해줍니다.

 

3. 코드

//https://www.acmicpc.net/problem/10986
//10986. 나머지 합(Gold 3, 누적합)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

#define endl "\n"
#define INT_INF 2147483647
#define LL_INF 9223372036854775807
#define ll long long
using namespace std;

ll N, M, ans = 0;
ll sumarr[1000000];
//sumarr의 나머지를 세는 배열
ll marr[1000];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    //INPUT
    cin >> N >> M;

    //SOLVE
    //누적합 계산
    ll sum = 0;
    ll A;
    int cnt = 0;
    for(int i = 0; i < N; i++) {
        cin >> A;
        if(A % M == 0) cnt++;
        sum += A;
        sumarr[i] = sum;
    }

    //구간합 (sumarr[j] - sumarr[i-1]) & M = 0 이라면
    //(sumarr[j] % M) - (sumarr[i-1] % M) = 0 이므로 
    //(sumarr[j] % M) = (sumarr[i-1] % M)) 인 경우의 수를 찾자.
    for(int i = 0; i < N; i++) {
        marr[sumarr[i] % M]++;
    }
    for(int i = 0; i < M; i++) {
        //후보들 중 2개를 순서상관없이 고르는 경우의 수
        ans += marr[i] * (marr[i] - 1) / 2;
    }
    //marr[0]에 들어갔던 구간합은 자기 자신만으로도 해당되기 때문에 따로 더해줌
    ans += marr[0]; 

    //OUTPUT
    cout << ans;
}

 

 

4. 이모저모

개인적으로 여러번 실수했던 부분이 있습니다.

바로 나머지를 세주는 marr의 자료형을 int로 선언하여 오버플로우가 계속 발생한 것입니다.

marr를 int로 선언한 배경은 marr의 원소가 한곳에 몰려서 아무리 커봤자 N의 최대값인 10^6을 넘지 못하기 때문에

int로도 충분하다고 생각하였습니다. 

하지만 ans += marr[i] * (marr[i] - 1) / 2; 이 계산에서 int 범위를 넘기기 때문에 오버플로우가 발생한다는 사실을 백준 질문게시판을 통해 알게되었고 굳이 int를 쓰고 싶다면 저 계산식에서만

1LL * 을 더해주거나 int64_t(marr[i]) 등의 형 변환을 해주어야 한다는 것도 배웠습니다.

누적합 + 모듈러 연산의 성질 + 자료형 등등 많은 것을 배울 수 있는 문제였습니다.오늘 하루도 화이팅 하십쇼~~!!