[Do it! 알고리즘 코딩테스트: Chapter 3] 누적 합(Prefix Sum)

 

본 포스팅은 Do it! 알고리즘 코딩테스트: C++편을 토대로 공부한 내용을 정리하기 위한 포스팅입니다.

https://github.com/KwonKiHyeok/Do_it_Alogrithm_Coding_Test_with_Cpp

GitHub - KwonKiHyeok/Do_it_Alogrithm_Coding_Test_with_Cpp: Do it! 알고리즘 코딩 테스트: C++편

 

 

누적 합(Prefix Sum)

브루트 포스를 개선하기 위해 미리 누적된 합을 저장해놓고 활용하는 기법이다.

즉, S[i]는 1번부터 i번까지의 합을 의미이다.

 

위 공식을 사용하면 O(1) 시간에 구간 합을 구할 수 있다.

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
	
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
		
	int N, M, A;
	cin >> N >> M;

	vector<vector<int>> arr(N+1, vector<int>(N+1, 0));

	for (int j = 1; j <= N; j++) {
		for (int i = 1; i <= N; i++) {
			cin >> A;
	
			arr[j][i] = A + arr[j-1][i] + arr[j][i-1] - arr[j-1][i-1];
		}
	}

	for (int i = 0; i < M; i++) {
		int x1, y1, x2, y2, sum = 0;
		cin >> x1 >> y1 >> x2 >> y2;
		
		sum = arr[x2][y2] - arr[x1-1][y2] - arr[x2][y1-1] + arr[x1-1][y1-1];
		cout << sum << '\n';
	}


	return 0;
}

 

 

#include <iostream>
#include <vector>
using namespace std;


int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M, A;
	cin >> N >> M;
	
	vector<long> C(M, 0);
	vector<long> arr(N, 0);
	cin >> arr[0];

	for (int j = 1; j < N; j++) {
		cin >> A;
		arr[j] = (arr[j - 1] + A);
	}

	long sum = 0;

	for (int i = 0; i < N; i++) {
		int remainder = arr[i] % M;

		if (remainder == 0) {
			sum++;
		}
		C[remainder]++;
	}
	for (int i = 0; i < M; i++) {
		if (C[i] > 1) {
			sum += C[i] * (C[i] - 1) / 2;
		}
	}

	cout << sum << '\n';
	return 0;
}

 

 난이도가 있는 누적 합 알고리즘 문제였다. 이 문제의 핵심 아이디어는 '(A + B) % C는 ((A % C) + (B % C)) % C와 같다'이다. 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값은 동일하다. 또한, S[j] % M의 값과 S[i] % M의 값이 같다면 (S[j] - S[i]) % M은 0이다. 즉, 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트하고 S[j]와 S[i]가 같은 (i, j)쌍을 찾으면 원본 배열에서 i + 1부터 j까지의 구간 합이 M으로 나누어떨어진다는 것을 알 수 있다. 따라서 같은 나머지를 가진 수들 중에서 2개를 선택하는 경우의 수를 구하기 위해 Combination을 진행하여 합을 구해 문제를 해결한다.