[백준/C++] 3673번: 나눌 수 있는 부분 수열

문제 & 링크

https://www.acmicpc.net/problem/3673

풀이

1. 수열의 원소를 입력받을 때, 해당 원소까지의 합을 d로 나눈 나머지를 저장한다. 합을 그대로 저장할 경우 sum이 너무 커지기에 비효율적이다.

2. d로 나눈 나머지가 나온 개수를 추가로 저장한다.

3. 같은 값을 가진 두 나머지가 있을 경우, 그 사이의 합은 d로 나누어 떨어진다. (예시 참고)

4. 같은 값을 가진 나머지가 n개일 경우 그 중 두 개(부분 수열의 시작점, 끝점)를 선택하면 되기에 조합(nC2)을 사용한다.

예시
1) d = 3이고, {1 4 2} 수열이 있을 경우
초깃값 0부터 시작하여 0 1 2 1 순서로 저장된다. 
-> 첫 번째 숫자는 초깃값 0, 두 번째 숫자는 (0 + 1) % 3 = 1, 세 번째 숫자는 (1 + 4) % 3 = 2, 네 번째 숫자는 (2 + 2) % 3 = 1
1이라는 나머지가 두 번 나왔기에 그 사이에는 3으로 나누어 떨어지는 부분 수열(2~3)이 1개(2C2) 존재한다.

2) d = 3이고, {1 1 1} 수열이 있을 경우
초깃값 0부터 시작하여 0 1 2 0 순서로 저장된다.
-> 첫 번째 숫자는 초깃값 0, 두 번째 숫자는 (0 + 1) % 3 = 1, 세 번째 숫자는 (1 + 1) % 3 = 2, 네 번째 숫자는 (2 + 1) % 3 = 0
0이라는 나머지가 두 번 나왔기에 그 사이에는 3으로 나누어 떨어지는 부분 수열(1~3)이 1개(2C2)  존재한다.

3) d = 3이고, {1 3 3} 수열이 있을 경우
초깃값 0부터 시작하여 0 1 1 1 순서로 저장된다.

-> 첫 번째 숫자는 초깃값 0, 두 번째 숫자는 (0 + 1) % 3 = 1, 세 번째 숫자는 (1 + 3) % 3 = 1, 네 번째 숫자는 (1 + 3) % 3 = 1
1이라는 나머지가 세 번 나왔기에 그 사이에는 3으로 나누어 떨어지는 부분 수열 {2~2}, {2~3}, {3~3}이 3개(3C2)  존재한다.

코드

#include <iostream>
#include <vector>
#include <map>

using namespace std;

vector<int> cnt;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;

    while (T--) {
        int d, n;
        cin >> d >> n;

        // 벡터 초기화
        cnt = vector<int>(d, 0);

        int sum = 0; // 0번 인덱스의 값은 0
        cnt[0]++; // map에 0의 개수 추가

        int num;
        for (int i = 1; i <= n; i++) {
            cin >> num;

            // 현재까지의 합을 d로 나눈 나머지를 저장
            sum = (sum + num) % d; 
            cnt[sum]++;
        }

        long long ans = 0; // 최대 50,000 * 50,000의 답이 나올 수 있기에 long long 선언
        for (int i = 0; i < d; i++) {
            // n개의 점 중 두 개(부분 수열의 시작점, 끝점)를 순서 없이 선택 -> nC2 (조합)
            // int 범위의 계산을 long long으로 바꿔주기 위해 1LL을 곱함
            ans += 1LL * cnt[i] * (cnt[i] - 1) / 2; 
        }

        cout << ans << "\n";
    }
}