백준 10986 나머지 합 C/C++

나머지 합 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

19410

5786

4234

28.212%

문제

수 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으로 나누어 떨어지는 구간의 개수를 출력한다.

예제 입력 1 복사

5 3
1 2 3 1 2

예제 출력 1 복사

7

 

 

#include <iostream>


using namespace std;

long arr[1005001], C[1005001] = { 0 }, S[1005001];
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n, m, rema;
	long cnt = 0;
	

	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
		
	}
	S[0] = arr[0];
	for (int i = 1; i < n; i++)
	{
		S[i] = S[i - 1] + arr[i];

	}

	for (int i = 0; i < n; i++)
	{
		
		rema = S[i] % m;
		if (rema == 0)
			cnt++;
		C[rema]++;
	}

	for (int i = 0; i < m; i++)
		cnt += (C[i] * (C[i] - 1)) / 2;

	printf("%ld", cnt);
	return 0;
}

 

 

각 구간의 합이 받은 값 m으로 나누어지는지 확인하는 문제다.

 

예제에서 

1 2 3 1 2를 받고 이것의 구간합이 3으로 나누어지는지 확인해보자.

 

우선 이를 일일이 계산해보면

1

1+2

1+2+3

1+2+3+1

1+2+3+1+2

 

2

2+3

2+3+1

2+3+1+2

 

3

3+1

3+1+2 

 

등등이 m(=3)으로 나누어지는지 확인해야 한다. 그러나 이는 시간이 너무 오래걸리기에 단축하는 방법이 필요하다.

여기서 우리는 (A+B) % C = ((A %C) + (B %C)) %C 의 공식을 이용하기로 하자.

 

예를 들어 7 %2 =1 이다. 3 %2 =1 이다. 

(7 + 3) % 2 = 0 = (1 +1) %2 가 된다.

각각의 나머지가 더해지기 때문에 결국 같게 된다.

 

이 논리를 이용하여 문제를 풀자.

 

1) 각각의 구간합 구하기

 

입력

1

2

3

1

2

구간합

1

3

6

7

9

 

위의 구간합을 보면 각각의 구간합은

1

1+2

1+2+3

1+2+3+1

1+2+3+1+2

이를 의미한다.

 

이 값을 M으로 나누어 떨어진다면 1부터 시작하는 구간합이 나누어 떨어지는지를 구할 수 있다.

1

0

0

1

0

0으로 된 부분은 나누어 떨어진 부분이고, 1로 된 부분은 나누어 떨이지지 않는 부분이다.

그렇다면 여기서 다시 2부터 계산을 한다면 시간이 오래걸린다.

그렇기에 위에 설명한 공식, (A+B) % C = ((A %C) + (B %C)) %C 에 따라 이를 계산한다.

 

나머지가 1인 구간끼리 빼면 나머지만큼 빼지기 때문에 이 부분은 나누어진다.

예를 들면 7%2 =1 이고, 3%2=1이다.

그럼 7-3 =4가 됨으로 나머지가 0이된다. 

나머지가 0인 부분에서도 마찬가지이다.

 

나머지가 0인 부분은 3개니까, 그 갯수는 3C2가 된다.

인덱스가 1,2,4가 0이라고 하면

(인덱스 4-2)  -1

(인덱스 4-1) - 2

(인덱스 2-1) - 3

총 3개의 경우의 수가 나온다.

 

또한 2C2를 통해 1인 것들의 갯수를 구할 수 있다.

이를 기존의 값에 추가해주면 문제를 풀 수 있다.