[백준/C++] 10986번 - 나머지 합

 

문제

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

 

수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.

 

즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

​

 

 

 

입력

 

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)

둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)

 

 

출력

 

첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.

 

 

풀이

 

처음에는 이전에 풀었던 누적 합 문제들과 비슷하다고 느꼈다. 그래서 처음에는 다음과 같은 순서로 코드를 짰다. (하지만 입력 범위를 보고 생각을 바로 고쳤다. 대충 봐도 N이 10^6일 때, 최소 (10^12)/2번 연산이 필요....)

​

[단순 풀이](시간초과)

 

1. N개의 숫자들을 입력받으면서 누적합을 구한다.

​

2. 누적합들의 나머지가 얼마인지 구해서 array에 저장한다.

ex) array의 idx가 1일 때는 1번째 숫자까지의 누적 합을 M으로 나눈 나머지, idx가 n일 때는 1~n번째 숫자까지의 누적 합을 M으로 나눈 나머지를 저장

​

3. array의 a번째 구간과 b번째 구간에 저장된 수를 뺐을 때, 차이가 0인 구간의 수를 센다.

문제는 입력의 범위를 보면서 N개의 수를 입력받기 때문에 구간을 비교하면서 Big O가 O(N^2)이기 때문에 시간초과가 날 것 같았다.

 

실제로 코드를 작성해 실행해본 결과 시간초과가 났고, 대략 어느 정도의 시간이 걸릴지 궁금했다. (찾아본 결과 시간 복잡도가 N^2일때 N이 10^6이면 약 16분이 걸린다고 한다...)

​

위에서 만든 array가 의미하는 것은 아래와 같다.

 

a번째 숫자부터 b번째 숫자까지의 합을 M으로 나눈 나머지를 구하기 위해서는 array[b]-array[a-1]를 이용하면 된다.

 

array[b]는 1~b번째 숫자를 더한 값을 M으로 나눈 값이 저장되어 있고, array[a-1]은 1~(a-1)번째 숫자를 더한 값을 M으로 나눈 값이 저장되어 있기 때문에 둘을 빼주면 a번째~b번째 숫자까지 더한 값을 M으로 나머지가 얼마인지 알 수 있다.

  

---

 

[두번째 풀이]

두번째 풀이는 나머지의 숫자를 이용한 방법이다.

 

n번째 구간까지의 합을 M으로 나눈 값들은 전부 0~(M-1)사이의 값들이기 때문에 우리가 원하는 나머지가 0이 되는 구간을 찾으려면 나머지의 수들을 세면 된다. (나머지가 0이 몇개인지, 1이 몇개인지... M-1이 몇개인지)

 

그래서 1번째 숫자부터 1~n번째 숫자까지의 구간합을 M으로 나눈 나머지의 갯수가 얼마인지 count 해 저장하는 array를 만들었다.

 

나머지의 갯수가 각각 얼마인지 알면 연속된 구간을 M으로 나눈 나머지가 0이 되는 구간이 몇개인지 알 수 있다. 왜냐하면 나머지가 2인 구간합들이 3개있다고 해보자(이하, 1~A번째 숫자를 더한 값을 M으로 나눈 나머지를 array[A]로 표현하겠다. 2인 구간은 A,B,C 3개이며 A < B < C 이다. )

 

그러면 array[B]-array[A]의 계산 값은 2 - 2 = 0 이다. 마찬가지로 array[C]-array[A], array[C]-array[B]도 0이다.

 

위와 같은 관계를 이용하면 나머지가 같은 구간이 몇개인지를 알면 나머지가 0이 되는 구간의 수를 알 수 있게 된다.

(여기서 나머지가 m인 구간이 n개라면 n*(n-1)/2 개의 구간의 나머지가 0이다. 조합을 생각하면 쉽다)

 

그러므로 0~(M-1) 사이의 나머지 갯수를 이용해 나머지가 0이 되는 구간이 몇개인지 세서 더해주면 된다.

 

이때 주의해야 할 점은 나머지가 0인경우는 나머지 갯수를 +1 해줘야한다. (1~n번째 구간의 나머지가 0일 경우 count가 되어야 하기 때문이다. 공집합을 생각하면 쉽다...)

 

 

Code

 

 

#include <iostream>
using namespace std;
long long func(long d) {
	return (d*d - d) / 2;
} //갯수를 세 반환할 함수

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

	int N, M;
	cin >> N >> M;
	int arr[1000]={ 0, }; //초기화
	arr[0] += 1; //초기화 
	
	int ipt = 0, a = 0; //ipt=n번째 숫자
	long long cnt = 0;
	for (int i = 0; i < N; i++) {
		cin >> ipt;
		a =(a+ipt)%M;
		arr[a] += 1; //구간 합의 나머지를 계산해 count
	}
	for (int i = 0; i < M; i++) {
		cnt += func(arr[i]);
	}
	cout << cnt;
}

 

---

분명히 코드를 제대로 짰는데 오류가 났었다.

 

이유는 출력해주는 값의 최댓값이 약 (10^12)/2 까지는 표현이 가능해야하는데 int형은 저장할 수 있는 값의 범위가 –2,147,483,648 ~ 2,147,483,647이기 때문이였다... 그래서 long long을 써서 값의 범위를 늘려줘서 해결했다. (파이썬은 이런거 생각 안해도 됐는데... ㅠㅠ)

 

 

 

 

 

10986번: 나머지 합