[백준알고리즘] 11660번: 구간 합 구하기 -C++

[백준알고리즘] 11660번: 구간 합 구하기 -C++

11660번: 구간 합 구하기 5 (acmicpc.net)

11660번: 구간 합 구하기 5

오랜만에 DP 문제를 풀어봤다. 그래서 쉬운 난이도를 골랐는데, 너무 쉬운 걸 고른 것 같기도 하다.

 

DP는 점화식만 잘 구하면 쉽게 문제를 풀 수 있다. 이 문제에서는 2개의 점화식을 구해야 한다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

---

문제 풀이

이번 문제는 행렬의 \((x1, y1)\)부터 \((x2, y2)\)까지의 값을 합한 값을 구하면 된다.

이때 아래의 2가지 종류의 점화식을 구했다.

1. \((0, 0)\)부터 \((x, y)\)까지의 구간합
2. \((x1, y1)\)부터 \((x2, y2)\)까지의 구간합

 

1번 점화식은 2번 점화식을 간단하게 만들기 위해 필요했다.

 

\(sum [i][j] = (0,0)\sim(i, j)까지의\ 구간합\)이라 하고, \(arr [i][j]=주어진\ 행렬의\ (i, j)\ 좌표의 값\)이라 할 때, 각 구간합 점화식은 다음과 같이 구했다.

1. \(sum [x][y] = sum [x-1][y]+sum [x][y-1]-sum [x-1][y-1]+arr [x][y]\)
2. \(sum [x2][y2] - sum [x2][y1-1] - sum [x1-1][y2] + sum [x1-1][y1-1]\)

단, 위의 \(x-1\), \(y-1\) 과 같이 \(1\) 을 빼는 값은 자연수일 때만 해당하며, 좌표값 \(x\) 또는 \(y\)가 \(0\) 인 경우에는 빼거나 더하지 않았다.

 

점화식은 직접 행렬을 그려서 더하는 구간과 뺄 구간을 체크하면서 확인하면 쉽게 파악할 수 있다.

 

따라서, 1번 점화식을 이용해서 \((0,0)\)부터 \((x, y)\)까지의 구간합을 구해준 뒤 행렬로 저장했다. 입력한 \((x1, y1), (x2, y2)\) 쌍에 대해 2번 점화식을 사용해 1번 점화식을 이용해 저장한 행렬의 값을 이용해 답을 출력하도록 했다. 

 

다음은 조금 더 어려운 동적 계획법 문제를 풀어보도록 해야겠다.

 

이번 문제의 통과 코드는 아래와 같다.

#include <cstdio>

const int MATRIX_MAX_SIZE = 1024;
const int PROBLEM_MAX_CNT = 100000;
const int COORDINATE_PAIR = 4;

unsigned int arrInput[MATRIX_MAX_SIZE][MATRIX_MAX_SIZE] = { 0, };
unsigned int arrSum[MATRIX_MAX_SIZE][MATRIX_MAX_SIZE] = { 0, };
unsigned int arrProblem[PROBLEM_MAX_CNT][COORDINATE_PAIR] = { 0, };

int main(void) {
	/* 입력 */
	int iMatrixSize = 0;
	int iProblemSize = 0;
	scanf("%d %d", &iMatrixSize, &iProblemSize);

	// 배열 입력
	for ( int iCol = 0; iCol < iMatrixSize; ++iCol ) {
		for ( int iRow = 0; iRow < iMatrixSize; ++iRow ) {
			scanf("%u", &arrInput[iCol][iRow]);
		}
	}

	// 문제 입력
	for ( int iCnt = 0; iCnt < iProblemSize; ++iCnt ) {
		for ( int iCoordinate = 0; iCoordinate < COORDINATE_PAIR; ++iCoordinate ) {
			scanf("%d", &arrProblem[iCnt][iCoordinate]);
		}
	}

	/* (1,1) ~ (x,y) 구간합 계산 */
	for ( int iCol = 0; iCol < iMatrixSize; ++iCol ) {
		for ( int iRow = 0; iRow < iMatrixSize; ++iRow ) {
			arrSum[iCol][iRow] = ((0 < iCol) ? arrSum[iCol - 1][iRow] : 0)
				+ ((0 < iRow) ? arrSum[iCol][iRow - 1] : 0)
				- ((0 < iCol && 0 < iRow) ? arrSum[iCol - 1][iRow - 1] : 0)
				+ arrInput[iCol][iRow];
		}
	}

	/* 출력 */
	for ( int iCnt = 0; iCnt < iProblemSize; ++iCnt ) {
		int iStartCol = arrProblem[iCnt][0] - 1;
		int iStartRow = arrProblem[iCnt][1] - 1;
		int iEndCol = arrProblem[iCnt][2] - 1;
		int iEndRow = arrProblem[iCnt][3] - 1;

		printf("%u\n", arrSum[iEndCol][iEndRow] 
			- ((0 < iStartCol) ? arrSum[iStartCol - 1][iEndRow] : 0)
			- ((0 < iStartRow) ? arrSum[iEndCol][iStartRow - 1] : 0)
			+ ((0 < iStartCol && 0 < iStartRow) ? arrSum[iStartCol - 1][iStartRow - 1] : 0));
	}

	return 0;
}