[Algorithm] Baekjoon 10986번 : 나머지 합

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

 

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
 
using namespace std;
 
 
int n, m, num;
long long modCounts[1001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    long long sum = 0;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> num;
 
        sum += num;
        ++modCounts[sum % m];
    }
 
    long long answer = 0;
 
    for (int i = 0; i <= 1000; ++i)
    {
        answer += modCounts[i] * (modCounts[i]-1) / 2;  // nC2
    }
 
    cout << modCounts[0] + answer;
}
 
 

 

 

 

 

https://cocoon1787.tistory.com/396

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

 

설명은 이분것을 참고했다. 한번에 이해가 잘 됐다.

 

문제를 푸는 핵심은 결국 모듈라연산의 식에서 뽑아오는것이였다.

 

어떤 i인덱스와 j인덱스 사이의 연속합을 구하려하면 보통 j까지의 누적합을 전부 구한 후, sum[j] - sum[i-1]을 한다.

이 때, 이 sum[j] - sum[i-1]을 m값으로 나눴을 때 나머지가 0이되는 모든 경우의 수를 구하는 문제이다.

 

(sum[j] - sum[i-1]) % mod = 0  이라면, 모듈라공식에 의해

(sum[j] % mod) - (sum[i-1] %mod) = 0이 되고, 이것은 결국

sum[j]  % mod = sum[i-1] % mod 가 된다.

 

즉  sum[1] % mod 값과 sum[3] % mod값이 같다면, 1과 3사이의 연속구간합을 m으로 나눴을 때 나머지값은 반드시 0이 된다.

그러니 우리는 sum[?] % mod 했을때의 값을 카운팅해놓으면 된다.

그저 경우의수만 구하면 되니까.

 

예를들어 sum[1], sum[2], sum[3]은 각각 %mod 했을 때 1이라고 해보자.

그러면 %mod했을 때 1인것들이 3개있다는 것이다.

그러니 이것들로만 구간을 형성하면 문제에서 요구하는 경우의수가 된다.

 

(1,2) 이렇게하던가 (1,3), (2,3)  이렇게하면, 문제에서 요구하는 %mod했을 때 나머지값이 0이되는 경우의 개수들이다.

그러면 이 경우의개수를 어떻게 빨리 구할것인가?

눈치가 빠르다면 알 수 있는데 그냥 조합이다.

위의 예시를 들자면, 3개의 선택지중에서 2개를 순서없이 고르는 경우의 수이다. 그러니 조합이다.

 

그리고 유의해야할 점은, 위 코드의 정답출력라인에 modCounts[0]을 추가로 더해주는게있는데, 이건 나머지가 0인것들의 인덱스를 end로 하고, 0을 start로 하는 경우가 존재하기 때문이다.

예를들어 나머지값이 0이되는 인덱스가 1,2,3이라 할 경우 기존에 (1,2), (1,3), (2,3) 외에도

(0,1), (0,2), (0,3) 이 존재한다.