백준 11660번
오늘 풀어본 문제는 백준의 11660번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
$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