골드3 - 백준 3673 나눌 수 있는 부분 수열

백준 3673 나눌 수 있는 부분 수열

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

접근방법

어떤 수로 나누어 떨어진다는 의미는 나머지가 0이라는 의미이고, 두 수의 나머지를 뺏을 때, 0이 나오면 나누어 떨어지는 것이다. 모든 조합을 구해주기 위해서 1~1, 1~2, 1~3, ..., 1~N까지 더한 값의 나머지를 전부 구해서 배열에 개수를 저장해주었고, 1~1, 1~2, ..., 1~N까지 나머지를 순서대로 빼주면서 개수를 구했다.

풀이

rest_num 배열을 이용해서 조합에서 나올 수 있는 나머지의 개수를 저장해주었다. 1~1, 1~2, ..., 1~N까지 나머지의 개수를 저장해주었고, 다시 각각의 범위를 차례로 빼주면서 나머지의 개수를 구해주어 result에 더해주었다. 이때 rest_num에서 그 범위의 나머지는 다시 등장할 수 없으므로 1씩 빼주었다.

코드

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int rest_num[1000000];
vector<int> numbers;

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

	int T;
	cin >> T;

	while (T--)
	{
		memset(rest_num, 0, sizeof(rest_num));
		numbers.clear();
		int d, n;
		cin >> d >> n;

		for (int i = 0; i < n; i++)
		{
			int num;
			cin >> num;
			numbers.push_back(num);
		}

		int temp = 0;
		for (int i = 0; i < n; i++)
		{
			temp += (numbers[i] % d);
			temp %= d;
			rest_num[temp] += 1;
		}

		int result = 0;
		int except = 0;
		result += rest_num[0];
		for (int i = 0; i < n; i++)
		{
			except += (numbers[i] % d);
			except %= d;
			result += --rest_num[except];
		}

		cout << result << '\n';
	}
	return 0;
}