본문 바로가기
카테고리 없음

백준 10986 : 누적합

by Fel.Forest 2025. 5. 25.

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

참고 : https://banwolcode.tistory.com/47


문제

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

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

입력값 : (1 <= n <= 10^6, 2 <= M <= 10^3) , (0 <= A <= 10^9)


생각

  1. 2차원 배열로 하나씩 확인하는게 방법인가?
  2. 일단 누적합인데
  3. n 번째에서 n-1번까지 확인해야 하기 때문에 이건 너무 n(n-1)/2 번인데 -> 이건 시간초과날꺼 같고
  4. 그렇다고 크기가 1인 것에서 n인거 까지 하나씩 늘려서 확인하는것도 같은 복잡도..
  5. 순서가 보장 되어 있는것도 아니고..
  6. 뭐 일단은 나머지에대한 것들로 해볼까..
  7. 아무리 생각해도 현재 내 능력치로 풀 수 없는 문제 -> 인터넷 검색

코드

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

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

    int n, m;
    cin >> n >> m;

    vector<ll> nums(n+1, 0);
    vector<int> remainders(m, 0);

    for(int ix = 1; ix <= n; ++ix)
    {
        int num;
        cin >> num;
        nums[ix] = (nums[ix-1] + num);
        ++remainders[nums[ix] % m];
    }

    
    // 일단 바로 나누어 떨어지는것
    ll count = remainders[0];
    // 나머지가 같은 것끼리 조합해서 푸는 방식
    for(int ix = 0; ix < m; ++ix)
    {
        // 없는 갯수에 대한 것은 기본으로 0 * -1 이 되기 때문에 고민할 필요가 없음
        // 최소한 2개는 골라야 하기 때문에 1개인 것도 1 * 0 이 되어서 걸러짐
        count += remainders[ix] * (remainders[ix] - 1) / 2;
    }

    cout << count;

}

틀린 이유

vector<int> remainders(m, 0);
  • 이 부분 최대 입력값이 10^6 인데 뭐가 문제인지 모르겠음

수정 코드

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

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

    int n, m;
    cin >> n >> m;

    vector<ll> nums(n+1, 0);
    vector<ll> remainders(m, 0);

    for(int ix = 1; ix <= n; ++ix)
    {
        int num;
        cin >> num;
        nums[ix] = (nums[ix-1] + num);
        ++remainders[nums[ix] % m];
    }

    
    // 일단 바로 나누어 떨어지는것
    ll count = remainders[0];
    // 나머지가 같은 것끼리 조합해서 푸는 방식
    for(int ix = 0; ix < m; ++ix)
    {
        // 없는 갯수에 대한 것은 기본으로 0 * -1 이 되기 때문에 고민할 필요가 없음
        // 최소한 2개는 골라야 하기 때문에 1개인 것도 1 * 0 이 되어서 걸러짐
        count += remainders[ix] * (remainders[ix] - 1) / 2;
    }

    cout << count;

}

 


결과

  • 문제 풀이 시간 : 못 품
  • 메모리 : 9836 KB
  • 시간 :  152 ms

배운점 및 고칠점

  • 1시간 고민 했지만 나오지 않았음
  • 이런 누적합 문제에 대해 알게 됨
  • 아직도 이해가 안되는 int가 안됨 -> 이건 형변환에 대해 문제가 있던거.