1일차 (월) : 10986번, 나머지 합 ****(G3)

문제 : 누적합과 Combination을 통해 문제를 해결할 수 있다. 단순히 누적합을 저장한 배열을 2중 반복문을 돌리면 TLE가 발생한다.

풀이과정

1. 수열에 대한 누적합을 저장한다.
2. 누적합의 나머지가 같다면 (a- b)%k = 0이라는 성질을 이용한다.
3. i번째 합의 나머지를 저장하며, 0~k-1의 각각을 나머지로 갖는 합의 개수를 찾는다
4. 각각의 나머지에서 2개를 선택하는 경우의 수를 계산하여 더한다.
5. 더한 값을 출력한다.
6. 정답

풀이 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int main() {
    fastio;

    int n, k, t;
    long long cnt = 0;
    cin >> n >> k;
    vector<long long> v(n + 1, 0);
    vector<long long> x(k, 0);
    for (int i = 1; i <= n; i++) {
        cin >> t;
        v[i] = v[i - 1] + t;
    }
    for (int i = 0; i <= n; i++)
        x[v[i] % k]++;
    for (int i = 0; i < k; i++)
        cnt += x[i] * (x[i] - 1) / 2;

    cout << cnt;

    return 0;
}

최종수정 : 2025-01-20