누적 합

백준 10986 나머지합 문제풀이

굉장히 오랜만에 블로그로 돌아왔다. 폐관수련 중이였다. 백준티어도 골드2정도로 올렸고 여러가지 자료구조들과 알고리즘들을 익혔다.
이제 본격적으로 포스팅도 해가며 공부를 할 계획이다. 이제 백준 플레티넘과 코드포스 블루를 향해 달려보도록 하겠다.
이후에 고수가 된다면 공부방법도 포스팅해봐야지 그 시작으로 누적합관련 문제..
백준 10986 나머지 합을 풀어보도록 하자 10986 나머지 합.

문제상황 파악하기.

나머지 연산(moduler 연산)에 관련되어있고 누적합을 이용하여 시간 복잡도를 줄여야한다.
for문을 두번 써서 계산하면 O(N^2)의 시간 복잡도를 가지는데 N이 최대 1000000이므로 이문제는 O(N)으로 풀어야한다.
그러면 자연스럽게 누적합을 써야겠단 생각이든다.

아이디어 얻기.

(A+B)mod m = A mod m + B mod m.
(A-B)mod m = A mod m - B mod m moduler연산에서 성립한다.
그러므로 모든 누적합들을 미리 m으로 나누어둬도 상관없다.
그러면 누적합을 구하고 맨 같은 수가 몇개인지 센후 이항계수를 다 더해주면 정답이 될것이다.

주의할 점.

그렇다면 정답의 최댓값은 무엇이 될까 이항계수 binomal(1000001,2)가 최대가 될것이고 이 값은 int범위를 넘어간다.
그러니 답은 long long 형으로 해주기로 하자.
하지만 연산 과정에 int가 있으면 int로 바꾸니 모든 변수를 long long으로 바꿔주겠다.

실제 코드.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

long long cumsum[1000001];    //누적합 저장
long long modrlt[1001];   // 나머지가 몇개인지 카운트

int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    
    int n,m;
    cin >> n >> m;
    
    cumsum[0] = 0;
    modrlt[0]++;
    for(int i=1;i<=n;i++){
        long long num;
        cin >> num;
        cumsum[i] = cumsum[i-1] + num;
        modrlt[cumsum[i]%m]++;
    }
    
    long long result=0;
    for(int i=0;i<1001;i++){
        result += modrlt[i]*(modrlt[i]-1)/2;
    }
    
    cout << result;
}