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

[ 문제 ]

 

 

 

[ 구현 ]

 

누적합 문제인데 그냥 누적합 문제가 아니라 나머지를 활용해야 한다.

 

여기서 핵심 아이디어는 나머지 연산을 활용하여

m으로 나눈 나머지를 누적합으로 구해놓고

i번째 인덱스와 j번째 인덱스가 같으면 i+1 ~ j까지의 합이 m으로 나눠떨어진다는 것이다.

 

예시를 들면

 

n=5, m=3

1 2 3 1 2로 입력이 주어졌을 때,

 

누적합 배열은 해당 인덱스번째까지의 누적합을 3으로 나눈 값을 저장

1 0 0 1 0

 

하지만 이 상태로 그냥 연산을 돌리면 시간초과의 우려도 있을 뿐더러(n^2, n<=10^6)

0으로 인한 중복상황이 생겨 구현자체가 힘들다.

 

따라서 2번째 핵심 아이디어는

1 0 0 1 0와 같은 배열 전체에서 같은 숫자를 찾아 2개를 고르는 방식이다.

 

같은 숫자들 중 2개를 조합하면 그 사이가 m으로 나눠지므로

나머지 누적합 배열에서 0~m-1까지의 숫자들이 각각 몇 번 나왔는지 저장하고

이를 활용하여 2번 이상 나온 모든 경우에 대해 nC2를 구해 더해주면 된다.

 

마지막으로 값이 0인경우 맨 앞에서부터 더해온 누적합을 m으로 나눈 것이 0임을 의미하므로 추가적으로 더해준다.

 

 

 

 

[ 코드 ]

 

#include <iostream>

using namespace std;

int dp[1000001];//1부터 index까지의 구간합을 m으로 나눈 나머지를 저장
int arr[1001];//0~m-1의 나머지가 각각 몇 번 나왔는지를 저장하는 배열
int n, m;
long long ans = 0;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;

	int tmp;

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

	for (int i = 0; i < m; i++) {
		if (arr[i] >= 2) {
			ans += ((long long)arr[i] * (arr[i] - 1)) / 2;
		}
	}


	cout << ans + arr[0];

	return 0;
}

 

 

 

[ 마무리 및 느낀 점 ]

 

아이디어가 좋아야 풀 수 있는 문제였다. 제목에 주어져 있는 나머지 합이라는 힌트를 잘 캐치하면 조금 더 쉽게 접근할 수 있지 않았을 까라는 생각이 들었다.

 

처음에 제출했을 때 틀렸는데 그 이유는

ans += ((long long)arr[i] * (arr[i] - 1)) / 2;

부분에서 (long long)을 빼먹고 제출했을 때 오버플로우가 일어나는 점을 캐치하지 못했던 것이었고

덕분에 한동안 쓰지 않아 잊고 있었던 형변환을 되새김질 했다.