백준 11660번

오늘 풀어본 문제는 백준의 11660번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 4

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

$N \times N$ 개의 수가 $N \times N$ 크기의 표에 채워져 있다. $(x1, y1)$ 부터 $(x2, y2)$ 까지 합을 구하는 프로그램을 작성하시오. $(x, y)$ 는 $x$ 행 $y$ 열을 의미한다.

예를 들어, $N = 4$ 이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

\begin{array}{|c|c|c|c|} \hline 1 & 2 & 3 & 4 \\ \hline 2 & 3 & 4 & 5 \\ \hline 3 & 4 & 5 & 6 \\ \hline 4 & 5 & 6 & 7 \\ \hline \end{array}

여기서 $(2, 2)$ 부터 $(3, 4)$ 까지 합을 구하면 $3+4+5+4+5+6 = 27$ 이고, $(4, 4)$ 부터 $(4, 4)$ 까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

입력

첫째 줄에 표의 크기 $N$ 과 합을 구해야 하는 횟수 $M$ 이 주어진다. ( $1 \leq N \leq 1024$ , $1 \leq M \leq 100,000$ ) 둘째 줄부터 $N$ 개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 $M$ 개의 줄에는 네 개의 정수 $x1, y1, x2, y2$ 가 주어지며, $(x1, y1)$ 부터 $(x2, y2)$ 의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 $1,000$ 보다 작거나 같은 자연수이다. ( $x1 \leq x2$ , $y1 \leq y2$ )

출력

총 $M$ 줄에 걸쳐 $(x1, y1)$ 부터 $(x2, y2)$ 까지 합을 구해 출력한다.

풀이과정

1번째 시도

이 문제를 읽고 DP를 활용하는 문제라는 것을 바로 알 수 있었다. 내가 이 문제를 해결한 방식은 입력을 받은 뒤 각각 가로 방향과 세로 방향으로 합을 누적 시키고, 두 좌표 사이에 있는 값들을 더하는 식을 누적 시킨 배열에서 $4$ 개의 원소의 합과 차로 나타내어 해결하였다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

int arr[1025][1025] = { 0, };

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, M;
	cin >> N >> M;

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

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

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

	for (int i = 0; i < M; i++) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;

		cout << arr[x2][y2] - (arr[x1 - 1][y2] + arr[x2][y1 - 1] - arr[x1 - 1][y1 - 1]) << "\n";
	}

	return 0;
}

그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.

마무리

오늘은 나의 PS 수련에 있어서 나름대로 의미가 있는 날이었다. 내가 PS 수련을 본격적으로 시작할 때는 CLASS 2의 에센셜 문제를 다 풀어둔 상황이었고, 그 이후로 차근차근 CLASS 2 마스터, CLASS 3, CLASS 3 에센셜을 도달해 왔다.

그리고 오늘에 이르러 드디어 CLASS 3 마스터를 달성하게 되었다!

(수정: 2024-06-09) 라고 생각했는데 아니었다! 솔브드 업데이트로 인해 아직 더 풀 문제들이 몇 개 남아있다. 아래의 감상은 굳이 지우진 않고 남겨두겠다.

이걸 이야기하는 이유는, 앞으로 PS를 진행하는 방식이 살짝 변경될 것이기 때문이다. 이제까지는 매일 CLASS 4 최소 한 문제, CLASS 3 몇 문제를 풀어오는 방식으로 진행해왔는데, 더 이상 풀어볼 CLASS 3 문제가 없기 때문에, 이틀에 한 번 CLASS 5 최소 한 문제, 하루에 CLASS 4 한 문제 이상을 풀어보는 방식으로 진행할 것이다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/11660

← Previous Post Next Post →