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

 

 

문제

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

 

정답 코드

#include <iostream>
#include <algorithm>
using namespace std;
long long input[1000001];
long long input_sum[1000001];
long long same_num[1001];
long long make_len(long long same){
	long long ret = 0;
	if (same >= 2){
		ret = (same * (same -1)) / 2;
	}
	return ret;
}

int main(){
	long long n,m;
	cin >> n>> m;
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	long long ret = 0;
	for (int i=1; i<=n;i++){
		cin >> input[i];
		input_sum[i] = (input[i] + input_sum[i - 1]);
		same_num[input_sum[i] % m]++;
	}
	same_num[0]++;
	for (int i=0;i <= m; i++){
		ret += make_len(same_num[i]);
	}
	cout << ret<< "\n";
}

문제 풀이의 흐름

• 일단 첫번째로 누적합에 대한 개념이 필요합니다

• 일정 구간까지의 합이 M으로 나누어 떨어진다는 것을 다르게 생각해보겠습니다.

• 누적합을 먼저 구하고 각 누적합을 M으로 나눈 나머지가 같은 값의 각각의 갯수를 구합니다.

• 나머지가 같다는 건 누적합에 2개의 범위를 뺏을 때 나누어 떨어진다는 의미입니다.

예를 들어서 설명을 진행해보겠습니다

• M은 3이고 들어온 입력은 1, 3 ,1 인상황을 가정해본다면

• 누적합은 1, 4, 5입니다 각각 3으로 나눈 나머지라고 가정을 해보면 1, 1, 2 가 됩니다.

• 그리고 1과 1을 동시에 선택하면 둘의 차를 구해서 3이 나옵니다. 즉 나머지가 같은 두개의 경우를 선택하면 됩니다.

• 다른 예시를 보면 1,2,1,2,1,2 이고 M이 3인 상황을 다시 가정해보겠습니다.

• 누적합을 계산해보면 1,3,4,6,7,9 가 됩니다.

• 이 누적합을 M값인 3으로 다시 나눠보면 1,0,1,0,1,0이 됩니다.

• 여기서 주의할점이 나오는데 시작할 때 구간을 0부터 시작하는 구간이라고 생각해야합니다. 왜냐하면 0으로 나누어 떨어지는건 혼자서도 존재할 수 있기 때문에 앞에 0을 하나 넣어주면 그걸 자연스럽게 해결 할 수 있습니다.

• 따라서 0이 4개 1이 3개이므로 4개중에 2개 선택 2개중에 2개 선택으로 4C2 + 3C2를 해서 6+3 하면 9개의 경우가 나오게 됩니다.

• 따라서 이것의 정답은 9가 됩니다.

주의 할 점

• 저는 나누어 떨어지는 것을 0은 3으로 나누어 떨어지지 않는다고 생각하고 아에 다르게 예외처리를 했는데 그렇게 할 필요가 없었습니다.

• 추가적으로 int만 정답으로 생각하고 틀린 이유를 한참 찾다가 long long 범위를 틀렸다는 걸 알게 되었습니다.

반성 및 고찰

• 예외 처리가 복잡해지면 내가 문제 이해를 잘못한게 아닌지 확인해보자.

• 로직상 맞는 것 같을 때는 범위로 overflow가 발생하는게 아닌지 확인해보자.