백준 10986번 나머지 합 (C++)

10986번: 나머지 합

문제 분석

위 문제는 배열의 모든 조합이 M에 대해 나누어 떨어지는가에 대해 묻고있다.

처음 문제를 접했을 때, 구간 합에 대한 개념을 알고 있다면 쉽게 풀 수 있다는 생각이 드는 문제이다.

구간 합을 모르는 사람이라면, 아래 링크를 통해 공부하고 오길 바란다.

백준 11660번 구간 합 구하기5 (C++)

---

합 배열을 만들고, 합 배열이 가질 수 있는 모든 구간 합을 검사해, 나누어 떨어지는지 확인하는 방식으로 문제를 풀었다.

C++ 첫 번째 풀이

#include <iostream>
#include <vector>

using namespace std;

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

	int N, M, num = 0;
	cin >> N >> M;
	vector<int> vec(N);
	vector<int> sum(N + 1, 0);

	for (int i = 0; i < N; i++) {
		cin >> vec[i];
		sum[i + 1] = sum[i] + vec[i];
	} // 입력과 동시에 합 배열 만들기

	for (int i = 1; i < N + 1; i++) {
		int point = sum[i]; 
		for (int j = 0; j < i; j++) {
			if ((point - sum[j]) % M == 0)
				num++;
		}// point가 가질 수 있는 구간합을 모두 만들어 나누어 떨어지는지 확인
	}
	cout << num;

	return 0;
}

하지만 위 코드는 문제가 많다.

1. 시간복잡도가 높다. 이중 반복문을 사용하기에 문제의 제한 시간을 넘기게 된다. O(N^2)

2. 자료형의 범위가 너무 작다. int 자료형이 가질 수 있는 범위를 초과하는 수가 나올 수 있다.

   -> 문제 조건에서 배열의 하나 원소에 대해 10^9에 대한 범위가 있고, 이에 대한 합 배열을 사용하기에 overflow가 발생한다.

---

문제 해결

첫 번째 문제해결을 위해서는, 반복문이 1번만 사용되어야 한다. 즉 아예 다른 알고리즘을 가져가야한다.

합 배열의 전체를 M의 숫자로 나눈다. 

1 2 3 1 2 일 경우, 1 3 6 7 9의 합배열이 있고, 이는

1 0 0 1 0으로 된다.

-> 처음부터 자신의 index까지의 합이 나누어 떨어진다.     +3

 

중요!

합 배열에서, 자신이 가진 나머지의 수가 빠지면 그 숫자는 나누어 떨어지게 된다. ( 합배열 - 나머지 => M으로 나누어 떨어짐)

그러므로, 나머지가 같은 이들끼리의 조합으로 나누어 떨어질 수 있는 새로운 수를 만들 수 있게 된다. (0을 포함하여)

즉, 나머지가 0인 원소 3개 중, 2개를 고른다. 3C2 -> +3

나머지가 1인 원소 2개 중, 2개를 고른다. 2C2 -> +1

보충 설명 : (나누어 떨어지는 수 + 나머지) - (나누어 떨어지는 수 + 나머지) = 나누어 떨어지는 수

ex) (7 + 3) - (14 + 3) = 21

 

두 번째 문제는 int 자료형을 long long으로 설정하여 범위를 최대로 늘려준다!

---

C++ 두 번쨰 풀이

#include <iostream>
#include <vector>

using namespace std;

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

	int N, M;
	long long num = 0;
	cin >> N >> M;
	vector<int> vec(N, 0);
	vector<long long> sum(N + 1, 0);
	vector<long long> rest(M, 0);


	for (int i = 0; i < N; i++) {
		cin >> vec[i];
		sum[i + 1] = sum[i] + vec[i];
		rest[sum[i + 1] % M]++; // 나머지값과 같은 index에 ++ -> 나머지의 갯수 파악 가능
		if (sum[i + 1] % M == 0) {
			num++; // 합 배열에서의 원소가 나누어 떨어지면 ++
		}
	}

	for (int i = 0; i < M; i++) {
		if (rest[i] != 0) {// 나머지가 존재한다는 조건. 원소는 나머지 갯수
			num += (rest[i] * (rest[i] - 1)) / 2; // nC2에 대한 공식을 이용함.
		}
	}

	cout << num;

	return 0;
}

 

코드 리뷰는 언제나 환영입니다.