Beakjoon] 나머지 합 구하기 (백준 코테) = 구간합

문제주소 : https://www.acmicpc.net/problem/10986

10986번: 나머지 합

문제요약 : N개의 수가 주어진 경우 연속된 부분의 합이 M으로 나누어 떨어지는 구간의 개수를 구하라

 

풀이 : 연속된 부분의 합이라는 것부터 구간합을 계산해 놓고 구하는 것을 추측할 수 있다.
누적합을 구해놓고 나머지 연산을 처리 한 뒤 0인것들의 수를 세어둔다
구간합의 계산은 S[End] - S[Start] 이므로 S[End]와 S[Start]의 값이 같을 경우 앞의 식에 %M을 하면 무조건 0이 된다 
그러므로 위 값이 같은 경우의 수를 세어서 미리 세어둔 0인값의 수와 합치면 된다

 

 

코드는 아래 숨김

#include <iostream>
#include <vector>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    int n, m;
    std::cin >> n >> m;

    std::vector<long> ori_array(n, 0), sum_array(n, 0), count_array(m, 0);

    int temp;
    for (int i = 0; i < n; ++i) {
        std::cin >> temp;
        if(i ==0)
            ori_array[i] = temp;
        else
            ori_array[i] = ori_array[i-1] + temp;
    }

    long long result_count = 0;
    for (int i = 0; i < n; ++i) {
        sum_array[i] = ori_array[i] % m;
        if (sum_array[i] == 0)
            ++result_count;
        count_array[sum_array[i]]++;
    }


    for (int i = 0; i < m; ++i) {
        if (count_array[i] > 1)
            result_count += count_array[i] * (count_array[i] - 1) / 2;
    }

    std::cout << result_count;

    return 0;

}

 

알게 된 것 : 골드3의 난이도답게 단순 누적합을 미리 구해놓는 것만으론 풀 수 없었다.

풀이와 같이 누적합이 M 나머지 0이 되는것을 찾을 뿐만 아니라 구간구간에서도 S[End]와 S[Start]가 같아지는 상황을 계산해서 추가로 카운트해줘야 한다.
게다가 경우의 수를 순열로 계산하는 방법을 알아야 한다.( n! / r!(n-r)!)

여기서 r이 2일 경우 n*(n-1)/2로 계산 가능하다 (nC2 일때만 가능한 공식)