합 배열을 이용한 나머지 합 구하기

* Do it 코딩 테스트 책을 참고하여 작성하였습니다.

 

문제에 대한 설명은 따로 하지 않겠습니다. (백준 온라인 저지 10986번 문제 참고.)

 

문제의 핵심은 연속된 부분의 합이라고 생각합니다. 연속된 부분의 합이므로 주어진 배열을 합 배열로 만들어서 손쉽게 원하는 범위내의 원소들의 합을 구할 수 있습니다.

( 예를 들어, sum[]이 존재하고 인덱스 i,j(i<j)인 경우 sum[j] - sum[i] 를 하면 i+1 ~ j까지의 합을 구할 수 있습니다.)

 

다음의 핵심은 구간의 합의 나머지를 구한다는 것입니다. 나머지 연산자는 분배하여 연산이 가능합니다.

ex. (A + B)% N = A%N + B%N 

 

그러므로 합 배열로 만든 인덱스들을 M(M값은 입력으로 들어온다.) 값으로 나머지연산을 하여 값을 넣어준 다음, 같은 나머지 연산 값이 나오는 값들 중에서 순서를 정하지 않는 콤비네이션 계산을 합니다. ( n개인 경우 nC2 를 해준다.) 

두가지를 고른 후, 두 인덱스의 값(나머지 연산하고 나온 값)은 같기 때문에 두 인덱스를 빼면 최종적으로 나머지가 없는 것이 됩니다.

 

이렇게 모든 경우의 수를 구한 후, 나머지 연산을 한 배열의 인덱스들을 검사하여 0인 것들을 구합니다. (이는 처음 인덱스부터 해당 인덱스까지의 합의 나머지 연산이 0이라는 뜻이므로 이 또한 문제의 조건을 만족하므로 개수를 추가합니다.)

 

최종적으로 나오는 값을 출력/반환하게 되면 정답을 도출하게 됩니다.

 

아래의 코드는 입력값이 이미 받아졌다는 가정하에 만들어 놓은 함수 코드입니다. 

 

이로써 "나머지 합 구하기"문제에 대한 풀이를 마치겠습니다. 포바~!

void solution_005()
{
	vector<int> input = { 1,2,3,1,2 };
	int M = 3;
	// 입력값들을 합배열로 변환
	for (int i = 1; i < input.size(); i++)
	{
		input[i] += input[i - 1];
	}

	int count = 0;
	vector<int> list(M, 0);

	// M으로 나머지 연산을 해준다.
	for (auto& i : input)
	{
		i %= M;
		if (i == 0) count++;

		list[i]++;
	}

	for (auto& i : list)
		count += (i * (i - 1) / 2);

	cout << count;
}