I am dosa.

누적 합

백준 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;
}

Leave a comment

2024

D&C Optimization

3 minute read

분할정복을 이용한 다이나믹 프로그래밍 최적화

Back to top ↑

2023

Back to top ↑

2022

Greedy

2 minute read

백준 18186번 라면사기(large) 문제풀이

SCC

1 minute read

백준 4196번 도미노 문제풀이

LCA

2 minute read

백준 3176번 도로 네트워크 문제풀이

2-SAT

1 minute read

백준 16367번 TV Show Game 문제풀이

Hashing

2 minute read

백준 21162번 뒤집기 K 문제풀이

Tree DP

1 minute read

백준 1949번 우수 마을 문제풀이

Trie

1 minute read

Trie 자료구조 이해하기

Merge Sort

1 minute read

merge sort를 이용하여 inversion 개수세기

Segment Tree

2 minute read

백준 11505 구간 곱 구하기 문제풀이

BFS

1 minute read

백준 2206 벽 부수고 이동하기 문제풀이

기하

1 minute read

백준 2166 다각형의 면적 문제풀이

이분탐색

1 minute read

백준 12015 가장 긴 증가하는 부분 수열2 문제풀이

누적 합

1 minute read

백준 10986 나머지합 문제풀이

Stack

1 minute read

스택 구현하기 ========== 자료구조의 기본이라고 하면 스택 과 큐가 있다 백준 10828번에서 마주친 스택

정렬1

1 minute read

매우매우 많은 정렬이 있지만 그중 가장 안 어려운 3가지를 공부해보았다.

Back to top ↑