백준 10986 나머지 합

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다.

 

이 문제는 연속된 수들의 합중 M으로 나누어 떨어지는 수의 개수를 구하는 문제인데 시간 제한이 1초라서

 

O(N^2)의 복잡도로는 해결이 불가능하다. 따라서 입력받은 숫자들을 첫 번째부터 더하면서 나눈 나머지를 배열에 저장한 뒤

 

예를 들어 예제 입력인 1 2 3 1 2 라면 각각 3으로 나눈 1 0 0 1 0 이 된다. 이때 1과 1사이에 있는 연속 적인 수들의 합이 나누어 떨어지게 된다는 것을 알  수 있다. 즉 나머지가 동일한 숫자 들이 있으면 그중 어떤 2개를 뽑으면 그사이에서 나머지가 0인 것이 반드시 존재하게 된다. 따라서 존재 하는 나머지 들을 2개를 택하는 조합으로 생각해서 nC2로 생각하면 시간안에 해결 할 수 있다. 시간 제한이 있어서 조합을 생각하는게 어려운 문제였습니다.. 풀이를 보고 그저 감탄 했습니다.

 

코드입니다.

 

#include <iostream>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false);
	int N,M;
	long long sum[1001] = {0,};
	int asum = 0;
	long long fre = 0; // 오버 플로우 발생 가능성이 있으므로 long long 선언 
	
	cin>>N>>M;
	
	for(int i = 0; i < N; i++) {
		int x;
		cin >> x;
		asum = (asum + x) % M; // i번째 까지 입력 받은 수들의 합을 M으로 나눈 나머지를 저장 
		
		if(!asum)
			fre++;

		sum[asum]++; //나머지가 asum인 요소 개수 증가 
	}
	
	for(int i = 0; i < M; i++) { 
			fre += sum[i]*(sum[i] - 1) / 2; // sum[i] 의 개수 중 2개를 고르면 그사이의 합이 나머지가 0 이된다. sum[i]C2 
	}
	
	cout<<fre<<'\n';
	
	return 0;	
}