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

3673번 : 나눌 수 있는 부분 수열

---

문제)

양의 정수로 이루어진 수열이 주어졌을 때, 연속하는 부분 수열의 합이 d로 나누어 떨어지는 것의 개수를 구하는 프로그램을 작성하시오.

예를 들어, 아래와 같은 수열의 부분 수열 중 4로 나누어 떨어지는 것의 개수는 6개이다.

 

2, 1, 2, 1, 1, 2, 1, 2

 

다음과 같은 부분 수열은 합이 4로 나누어 떨어진다. 1~8, 2~4, 2~7, 3~5, 4~6, 5~7번째

 

 

 

입력 :

첫째 줄에 테스트 케이스의 개수 c가 주어진다. (1 ≤ c ≤ 200) 각 테스트 케이스는 두 줄로 이루어져 있다.

테스트 케이스의 첫째 줄에는 d(1 ≤ d ≤ 1,000,000)와 수열의 크기 n(1 ≤ n ≤ 50,000)이 주어진다. 다음 줄에는 수열의 원소가 주어진다. 각 숫자는 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 정수이다.

 

 

 

출력 :

각 테스트 케이스에 대해서, 주어진 수열의 연속하는 부분 수열의 합이 d로 나누어 떨어지는 것의 개수를 출력한다.

 

 

 

 

 

풀이)

 

// 3673. 나눌 수 있는 부분 수열
#include <iostream>
#include <vector>
#include <map>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int t;
    cin >> t;
 
    while (t--)
    {
        int n, d;
        cin >> d >> n;
 
        vector<long long> vec(n + 1, 0);
        vector<long long> prefix(n + 1, 0);
 
        for (int i = 1; i < n + 1; i++)
        {
            cin >> vec[i];
            prefix[i] = (prefix[i - 1] + vec[i]) % d;
        }
 
        map<long long, long long> cnt;
        cnt[0] = 1;
 
        long long answer = 0;
        for (int i = 1; i < n + 1; i++)
        {
            answer += cnt[prefix[i]];
            cnt[prefix[i]]++;
        }
 
        cout << answer << '\n';
    }
 
    return 0;
}

---

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

3673번: 나눌 수 있는 부분 수열