[C++] 백준 2167번 2차원 배열의 합

 

첫번째 줄에는 N*M의 배열 크기 입력

2번째 줄에는 N*M 배열 안의 배열값 입력

3번 째 줄에는 몇번 구할건지 횟수 입력

4번째 줄에는 x1,y1 ~ x2,y2 좌표 입력

총 x1,y1 ~ x2,y2의 배열의 합이 몇인지 찾는 문제입니다.

 

for문을 이용해서 값을 구하거나

다이나믹 프로그래밍을 통해서 문제를 풀 수 있습니다.

for문을 사용해서 문제를 풀면 DP에 비해서 시간이 많이 걸리게 됩니다.

 

다이나믹 프로그래밍으로 푼 방법은

먼저 모든 (Xn, Yn)좌표에 현재 위치부터 끝 지점까지의 총 합을 입력합니다.

for (int i = N; i >= 1; --i) {

for (int j = M; j >= 1; --j) {
	DP[i][j] = DP[i][j] + DP[i+1][j] + DP[i][j+1] - DP[i+1][j+1];
}

 

그리고 시작점과 끝점을 이용해서 결과값을 도출합니다.

sum = DP[startX][startY] - DP[startX][endY + 1] - DP[endX + 1][startY] + DP[endX + 1][endY + 1];

 

여기서 각각의 의미는 아래와 같습니다.

1. DP[startX][startY] = 시작위치에서 배열 끝까지의 합

2. DP[startX][endY + 1] = 시작지점X, 종료지점+1 Y위치 에서 배열 끝까지의 합

3. DP[endX + 1][startY] = 종료지점X+1, 시작지점 Y위치 에서 배열 끝까지의 합

4. DP[endX + 1][endY + 1]; = 종료지점X+1,  시작지점Y+1 위치에서 배열 끝까지의 합

 

1번은 시작부터 끝까지를 찾기때문에 종료지점이 넘는 부분을 빼주어야 합니다.

그래서 2번과 3번으로 넘는 지점을 전부 제거해줍니다.

하지만 2번과 3번에 교집합인 부분이 2번 제거 되었고

이를 해결하기 위해 제거된 부분인 4번 부분을 더해줍니다.

 

 

for문 코드

#include <iostream>
using namespace std;

int main(int argc, char *argv[])
{
	int N, M;
	int cycle;
	int sum;
	int startX, startY;
	int endX, endY;
	int map[310][310];

	cin >> N >> M;
	for (int i = 1; i <= N; ++i) {
		for(int j = 1; j <= M; ++j) {
			cin >> map[i][j];
		}
	}

	cin >> cycle;
	while (cycle-- > 0) {
		cin >> startX >> startY;
		cin >> endX >> endY;
		sum = 0;

		for (int i = startX; i <= endX; ++i) {
			for (int j = startY; j <= endY; ++j) {
				sum += map[i][j];
			}
		}
		cout << sum << endl;
	}


	return 0;
}

 

DP 코드

#include <iostream>
using namespace std;

int arr[301][301];
int d[301][301];
int n, m;

int main() {
   cin >> n >> m;
   for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
         cin >> arr[i][j];
         d[i][j] = arr[i][j] + d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];
      }
   }
   int k;
   cin >> k;
   while (k--) {
      int a, b, x, y;
      cin >> a >> b >> x >> y;
      cout << d[x][y] - d[a - 1][y] - d[x][b - 1] + d[a - 1][b - 1] << endl;
   }
   return 0;
}