개요

백준 10986: 나머지 합

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

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

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

접근 방식

1. 나머지가 같으려면 해당 구간의 첫값 이전의 합의 나머지와,
   해당 구간까지 포함한 전체 합의 나머지가 같아야 한다.
   서로 나머지가 같다면 결국 해당 구간의 나머지 값이 0이란 뜻이기 때문이다.
   ->
   인덱스 1~2구간의 합을 A,
   인덱스 3~5구간의 합을 B라고 하면
   인덱스 1~5 구간의 합을 A+B라고 표현할 수 있다.
   A % M = 1이고 (A + B)% M =1 이라고 하면 (A+B) % M = A % M + B % M이기 때문에
   A%M + B%M=1 -> 1+B%M=1 -> B%M =0

2. 따라서 Sum배열에 i번째 인덱스까지 더한후 M으로 나눠준 값을 저장해줘서 각 배열의 원소를
   비교하는 방식으로 풀었으나 시간초과가 났다.

   void Input() {
   	cin >> N >> M;
   	for (int i = 0; i < N; i++) {
   		cin >> inputArr[i];
   		//i번째값까지 나머지 더한 총합= Sum[i+1]
   		Sum[i + 1] = (Sum[i] + (inputArr[i] % M)) % M;
   		//0인값은 이미 답 충족
   		if (Sum[i + 1] == 0) rem[0]++;
   	}
   }
   
   void Solution() {
   	long long Ans = 0;
   	//나머지 같은 구간 갯수 증가
   	for (int i = 1; i < N; i++) {
   		for (int j = i + 1; j < N + 1; j++) {
   			if (Sum[i] == Sum[j]) rem[Sum[i]]++;
   		}
   	}
   	for (int i = 0; i < M; i++) {
   		Ans += rem[i];
   	}
   	cout << Ans;
   }

   Solution()함수 내에서 반복문이 두번돌아서 N이 범위의 최대값일때 시간초과가 났다.

3. 많이 고민해보고 검색한 결과, 저렇게 반복문 처리를 해주는 부분을 줄일 수 있는 방법을 알았다.
   저 반복문은 i가 1부터 N-1일때 j는 i+1부터 N까지 반복하며
   Sum[i]와 Sum[j]값이 같을 때, rem[Sum[i]]값을 증가시켜준다.

   이 말은 결국 Sum[i]의 값과 같은 모든 값의 쌍의 갯수를 찾는 방식이다.
   따라서 Sum[i]값의 총 갯수를 x라고 하면 모든 쌍의 갯수는 x*(x-1) /2개가 나온다.
   (1부터 x-1까지의 합)

   따라서 나머지의 갯수를 미리 저장해둔 후 마지막에
   (나머지 i인 구간 갯수)*( 나머지 i인 구간 갯수-1) /2 를 한 값을 더하면
   나머지 i인 구간의 쌍의 총갯수가 나온다.

   하지만 나머지가 0인 구간들은 다른 구간과 쌍을 안 이루고도 혼자 답을 충족시키므로
   나머지 0인 구간을 또 더해줘야한다.

   void Input() {
   	int inputInt = 0;
   	cin >> N >> M;
   	for (int i = 0; i < N; i++) {
   		cin >> inputInt;
   		//i번째값까지 나머지 더한 총합= Sum[i+1]
   		Sum[i + 1] = (Sum[i] + (inputInt % M)) % M;
   		//나머지값 다 저장 
   		rem[Sum[i + 1]]++;
   	}
   }
   
   void Solution() {
   	long long Ans = 0;
   	for (int i = 0; i < M; i++) {
   		//0~rem[i]-1값까지 더한 값이 Sum[i]값과 같은 값을 가진 인덱스와의 쌍의 개수다 
   		Ans +=(long long) rem[i]*(rem[i]-1) /2;
   	}
   	//마지막에 쌍을 안이뤄도 이미 0으로 나눠떨어지는 구간인 rem[0]의 갯수를 더해줘야함
   	cout << Ans+rem[0];
   }

   이런식으로 간단하게 구현이 가능하다.
   

전체 코드

#include<iostream>

using namespace std;

//index까지의 원소의 총합 % M값 저장한 배열
int Sum[1'000'002];
//각 index는 M으로 나눈 나머지가 같은 구간의 총 갯수
int rem[1001];

int N = 0, M = 0;
void Input() {
	int inputInt = 0;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> inputInt;
		//i번째값까지 나머지 더한 총합= Sum[i+1]
		Sum[i + 1] = (Sum[i] + (inputInt % M)) % M;
		//나머지값 다 저장 
		rem[Sum[i + 1]]++;
	}
}

void Solution() {
	long long Ans = 0;
	for (int i = 0; i < M; i++) {
		//0~rem[i]-1값까지 더한 값이 Sum[i]값과 같은 값을 가진 인덱스와의 쌍의 개수다 
		Ans +=(long long) rem[i]*(rem[i]-1) /2;
	}
	//마지막에 쌍을 안이뤄도 이미 0으로 나눠떨어지는 구간인 rem[0]의 갯수를 더해줘야함
	cout << Ans+rem[0];
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();
	Solution();
}

문풀후생

많이 막힌 문제였다.

나머지가 같은 구간을 판별하는 과정에서 막혔고

같은 나머지를 가진 구간합의 쌍의 갯수를 파악할때 반복문을 사용해 시간초과에 막혓다.

그 다음은 구현을 했을 땐, 입력값이 10억까지 들어오게 되므로 Solution함수의
답을 저장하는 Ans 변수가 int값을 넘어가는데 체크를 안 했다.

그 후에 막힌 부분은 Ans +=(long long) rem[i]*(rem[i]-1) /2; 이 부분이였는데
rem값이 int를 안 넘고, Ans값은 long long으로 선언해서 괜찮을 줄 알았다.
int*int값이 기본적으로 int값에 저장되어서 오버플로가 일어난다는 사실을 까먹었던 것..
long long으로 형변환해주니 통과되었다.