구간 합 문제 (모듈러 연산)

문제

젤다

수열이 주어지고, 그 수열들의 부분합중에서 m으로 나누어지는 값을 구하는 문제이다. 역시나 시간부족으로 틀린다.

그냥 풀기

#include <iostream>
using namespace std;

long n, m;
int count = 0;

int main() {
    cin >> n >> m;
    long arr[n+1];
    long sum[n+1];
    sum[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i-1] + arr[i];
    }
    cout << "\n";
    for (int i = n; i > 1; i--) {
        for (int j = 1; j <= i; j++) {
            if ((sum[i] - sum[j-1]) % 3 == 0) count++;
        }
    }
    cout << count;
}

브루트포스로 전부다 하나씩 방문해보는 방식이다.
당연히 시간초과다. 이렇게 풀렸다면 골3이 아니겠지...

모듈려 연산 쓰기

검색해본 결과 이 문제는
PrefixSum[j] - PrefixSum[i] ) % MOD = 0 이 만족한다면
PrefixSum[j] % MOD = PrefixSum[i] % MOD 도 만족하게 된다.를 이해해야만 풀 수 있는 것이였다.

그러면 천천히 살펴보도록 하자.
예제는

5 3
1 2 3 1 2

이다.

이를 표에 각 수와 prefixSum을 나타내면

0 1 2 3 4 5
0 1 2 3 1 2 
0 1 3 6 7 9

가 된다.

여기서 prefixSum들을 전부 mod 처리하면 다음과 같다.

0 1 2 3 4 5
0 1 2 3 1 2 
0 1 0 0 1 0

여기서 위의 조건인 j % mod = i % mod를 찾아보면

1 - 1인 (1, 4)
0 - 0인 (2, 3) (2, 5) (3, 5)
총 4개가 존재한다.

그리고 이 prefix % mod = 0인 것들은 첫번째 원소부터 n번째 까지 합이 mod 0이라는 뜻이기에 각 3개씩을 더해야한다.

따라서 1 + 3 + 3 = 7 이다.

도움이 된 코드 (https://cocoon1787.tistory.com/396)

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

long long n, m, val, sum;
long long cnt[1001];
long long ans = 0;

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> val;
        sum += val;
        cnt[sum % m]++;
    }
    
    ans += cnt[0];
	for (int i = 0; i <= 1000; i++) {
		ans += cnt[i] * (cnt[i] - 1) / 2;
	}
	
	cout << ans;
}

내가 실수한 점

1. arr 선언은 main 밖에 해야지, 안에다가 하면 0으로 초기화가 안된다.

2. 굳이 10^3승까지 돌 필요는 없다. 어차피 mod m은 최대값이 m - 1이다.

3. arr, sum array를 너무 많이 만들었다.

#include <iostream>
using namespace std;

int arr1[10];

int main() {
    int arr2[10];
    
    for (int i = 0; i < 10; i++) {
        cout << arr1[i] << " ";
    }
    cout << "\n";
    for (int i = 0; i < 10; i++) {
        cout << arr2[i] << " ";
    }
}

0 0 0 0 0 0 0 0 0 0 
875763392 383 1037047033 32758 1 0 7 0 875763360 383 

보이는것처럼 밖에 선언한 arr1은 0으로 전부 초기화가 되는데, 안에 선언한 arr[2]는 하나도 안된다.

정리

원리만 알면 쉽게 풀었을거같은데 몰라서 맞았다