[백준] 10986번 나머지 합 : 맞왜틀 - C++

들어가며

 맞왜틀, 맞는데 왜 틀려라는 뜻으로 코딩을 하다 보면 자신도 모르게 맞왜틀을 외치게 될 때가 있습니다. 경험상 보통 99.99%는 제가 틀린 것이지만요. 이런 맞왜틀을 마주칠 때 점검해 봐야 할 것은 무엇이 있을까요?

1. 변수명 확인: 똑같은 변수명을 함수 내외에서 선언하거나, 변수명을 헷갈려서 다르게 사용하는 경우도 있습니다.
2. 세미콜론: 여기서 세미콜론은 안 붙인 경우가 아니라 붙인 경우입니다. 안 붙이면 컴파일 에러가 뜨지만 while이나, for 뒤에 붙이게 되면.. 컴파일 에러도 안 뜨고 잘 안 보여서 찾기도 어렵습니다.
3. 오버플로우 & 언더플로우: int는 대충 21억 long long은 약 9*10^18까지가 범위입니다. 유형에 맞는 자료형을 써야 합니다.

 오늘 제가 한 실수는 3번 오버플로우였습니다. 오버플로우는 생각보다 자주 마주치게 되는데 아주 큰 int의 덧셈이나 곱셈을 사용할 때는 항상 의심해야 합니다.

나머지 합

문제

수 N개 A1, A2,..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai +... + Aj (i ≤ j)의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 10^6, 2 ≤ M ≤ 10^3)

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

출력

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

풀이 방법

 풀이 방법은 의외로 누적합을 풀어봤다면 어렵지 않습니다. m으로 나누어 떨어지는지 확인하면 되므로, 모든 누적합을 m으로 나눈 나머지가 같은 것 끼리 세면 됩니다. 나머지가 같은 누적합이 있다면 뒤쪽 누적합에서 앞쪽 누적합을 빼면 나머지가 0이 되므로 그 구간은 m으로 나누어 떨어진다는 것을 알 수 있습니다. 주의할 점은 처음에 아무것도 더하지 않으면 0인 구간이 있다는 것입니다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	cin.tie(nullptr)->sync_with_stdio(false);

	int n, m;
	cin >> n >> m;

	vector<int> modulus(m);
	modulus[0] = 1;

	int sum = 0;
	for (int i = 0; i < n; ++i)
	{
		int num;
		cin >> num;
		sum = (sum + num) % m;
		modulus[sum] += 1;
	}

	long long answer = 0;
	for (int i = 0; i < m; ++i)
	{
		int mdl = modulus[i];
		if (mdl < 2)
			continue;
		answer += (long long)mdl * (mdl - 1) / 2;
	}

	cout << answer;

	return 0;
}

 

 주의할 점은 조합의 개수를 세는 문제지만 조합의 개수가 int의 범위를 벗어날 수 있다는 것입니다. 또한 answer을 구하는 과정에서 int끼리의 곱셈이 있기 때문에 long long으로의 형 변환이 필요합니다. 여기서 mdl은 최대 10^9의 값을 가질 수 있는데, long long은 그의 제곱보다 큰 9*10^18까지 커버할 수 있기 때문에 long long이 필요한 것입니다.

마치며

 이제는 오버플로우에 조금 익숙해졌다고 생각했는데, 오버플로우는 럴커처럼 항상 숨어있는 것 같습니다. 다들 럴커 잘 피하시고 즐겁게 코딩하시기 바랍니다.