백준 11660 - 구간 합 구하기5

문제링크

• 백준 11660

문제 접근

• 그림과 같이 2차원 배열의 부분 면적에 속한 원소들의 합을 구하는 문제라고 직관적으로 이해하면 쉽다.
• 반복문을 중첩하여 해당 면적의 원소들을 일일이 더해가는 방법도 있겠지만 시간초과에 무조건 걸릴 것으로 판단했다. 또, 문제에서 의도하는 풀이방법은 아닐 것이다.
• 부분합을 구할 때 가장 많이 사용하는 방법은 a(n) = S(n) - S(n-1)의 원리를 이용하는 방법이다.
• 예를 들어, 3부터 10까지의 합을 구할 때 우리는 1부터 10까지의 합은 55라는 것을 통상적으로 알고 있으므로 55 - (1부터 2까지의 합) = (3부터 10까지의 합) 이 됨을 판단할 수 있다.
• 이 원리를 dp 알고리즘으로 접근하여 문제를 해결하였다.

의사코드(pseudo-code)

- input N, M
- init vector<vector<int>> prefix(N+1, vector<int>(N+1, 0))
- init sum = 0
- for i=1 to N do:
	- for j=1 to N do:
		- input an integer in a varaible, n
		- sum += n
		- prefix[i][j] = sum
	- if i>1 then:
		- prefix[i][0] = prefix[i-1][N]
- for k=0 to M-1 do:
	- init result=0
	- input x1,y1,x2,y2
	- for i=x1 to x2 do:
		- result += prefix[i][y2] - prefix[i][y2-1]
	- print "result"

소스코드 및 분석

전체 코드

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

int main()
{
	int N, M;
	scanf("%d %d", &N, &M);
	vector<vector<int>> prefix(N + 1, vector<int>(N + 1, 0));
	int sum = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			int n;
			scanf("%d", &n);
			sum += n;
			prefix[i][j] = sum;
		}
		if (i > 1) prefix[i][0] = prefix[i - 1][N];
	}

	for (int k = 0; k < M; k++) {
		int x1, y1, x2, y2;
		int result = 0;
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		for (int i = x1; i <= x2; i++) {
			result += prefix[i][y2] - prefix[i][y1- 1];
		}
		printf("%d\n", result);
	}
}

부분 코드

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

• 정적 메모리를 할당할 경우 스택 메모리의 초과로 프로그램이 정상적으로 실행되지 않는다. 따라서 벡터 컨테이너를 활용해 2차원 동적 배열을 형성한다.
• 문제에서 행렬의 시작을 1행 1열로 정했기 때문에, 2차원 배열의 모든 원소를 0으로 초기화하고 N+1 만큼의 메모리를 할당했다.

int sum = 0;
for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			int n;
			scanf("%d", &n);
			sum += n;
			prefix[i][j] = sum;
		}
		if (i > 1) prefix[i][0] = prefix[i - 1][N];
	}

• 2차원 배열의 원소들을 입력받으면서 해당 원소까지 부분합을 구하는 코드이다.
• prefix[i][j]에는 1행 1열부터 i행 j열까지의 원소들의 합이 대입된다.
• 주의할 점은, 만약 (x1,y1)=(1,1), (x2,y2)=(4,4) 인 경우처럼 부분합을 구할 때 열(column)에 해당하는 인덱스가 0을 가리키는 경우가 생길 수 있다. 우리는 초기화 단계에서 벡터의 모든 원소를 0으로 초기화하였기 때문에 2행 0열의 값은 1행 4열의 값이 아니라 0을 가진다.
• 따라서 2행부터 0열의 원소는 이전 행의 마지막 원소값을 대입해주어야 부분합 계산 과정에서 문제가 발생하지 않는다.

for (int k = 0; k < M; k++) {
		int x1, y1, x2, y2;
		int result = 0;
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		for (int i = x1; i <= x2; i++) {
			result += prefix[i][y2] - prefix[i][y1- 1];
		}
		printf("%d\n", result);
	}

• 위에서 언급했던 부분합 구하는 방법을 코드로 구현하였다.