문제 설명
문제 링크: https://www.acmicpc.net/problem/11660
풀이
이 문제는 이차원 배열의 부분 구간 합을 구하는 문제입니다.
짐작한 바와 같이, 단순히 (x1, y1) ~ (x2, y2) 구간의 값들을 합해서 답을 제시하면 시간제한에 걸립니다.
그래서 구하려고 하는 부분 구간의 합을, 계산하기 쉽고 빠른 전체 구간의 합에서 더 작은 구간의 합을 빼는 방식으로 문제를 풀려고 합니다.
전체 구간의 합은 더 작은 구간의 합으로 만들 수 있고, 그 작은 구간의 합을 저장해 뒀다면 빠르게 합을 구할 수 있습니다.
이렇듯, 동적 계획법이란 전체의 문제를 작은 부분 문제로 나누어 계산한 후, 이 계산의 결과를 사용하여 전체의 문제를 빠르게 푸는 방법입니다.
S(x, y)를 배열 처음부터 (x, y)까지 구간의 합이라고 하면,
S(x, y)는 아래 이미지처럼 더 작은 구간의 합으로부터 값을 구할 수 있습니다.
중복되는 부분이 있으므로, 그만큼의 값은 빼야 되는 것을 잊으면 안 됩니다.
S(x,y) = S(x, y-1) + S(x-1, y) - S(x-1,y-1) + a
여기서, a는 (x, y)에 있는 숫자입니다.
위의 식을 코드로 작성하면 아래와 같습니다.
S(1,1) = 1부터 시작해서 S(N, N)까지의 모든 구간의 합을 빠르게 계산할 수 있게 됩니다.
#define SIZE 1024
int num[SIZE+1][SIZE+1];
for( int i = 1; i <= N; i++){ // N x N 배열
for( int j = 1; j <= N; j++){
a = readInt(); // 배열에 들어갈 숫자를 읽는다
// (i,j)구간까지의 합을 이전의 값으로 부터 구한 후, 저장한다
num[i][j] = num[i][j-1] + num[i-1][j] - num[i-1][j-1] + a;
}
}
이제 이 결과를 이용해 부분 구간의 합을 구해 봅시다.
위의 이미지처럼 부분 구간의 합 A를 구하기 위해서, 전체 구간의 합에서 B와 C 구간의 합을 빼면 될 것입니다.
그런데, B와 C 구간에서 중복되는 부분이 있으므로 중복되는 부분의 합은 다시 더해줘야 합니다.
그러므로, 부분 구간 (x1, y1) ~ (x2, y2)의 합 A를 식으로 하면 다음과 같습니다.
여기서 S(x, y)는 위에서 정의했던 배열 처음부터 (x, y)까지 구간의 합입니다.
부분합 A = S(x2, y2) - S(x2, y1-1) - S(x1-1, y2) + S(x1-1, y1-1)
이 결과를 출력하면 문제 해결입니다.
// (x1,y1) ~ (x2,y2) 구간
x1 = readInt();
y1 = readInt();
x2 = readInt();
y2 = readInt();
int sum = num[x2][y2] - num[x2][y1-1] - num[x1-1][y2] + num[x1-1][y1-1];
원래 std::cin과 std::cout 객체를 사용하려고 했는데, 숫자들을 입력받는 시간 때문에 시간제한을 통과할 수가 없었습니다.
그래서, 한 번에 버퍼에 읽은 후, 값을 가져오는 방식을 사용했습니다.
소스 코드
#include <iostream>
// 입출력 소스 --------------------------------------------
#define WBUF_SIZE (1 << 20)
char rbuf[WBUF_SIZE];
char wbuf[WBUF_SIZE];
int widx, ridx, nidx;
inline char read() {
if (ridx == nidx) {
nidx = fread(rbuf, 1, 1 << 20, stdin);
if (!nidx) return 0;
ridx = 0;
}
return rbuf[ridx++];
}
inline int readInt() {
int sum = 0;
char now = read();
bool flg = false;
while (now <= 32) now = read();
if (now == '-') flg = true, now = read();
while (now >= 48) sum = sum * 10 + now - '0', now = read();
return flg ? -sum : sum;
}
int unitSize(int n) { // 자리 수
if (n < 0)n = -n;
int ret = 1;
while (n >= 10) {
ret++;
n /= 10;
}
return ret;
}
void wbflush() {
fwrite(wbuf, 1, widx, stdout);
widx = 0;
}
void write(char c) {
if (widx == WBUF_SIZE) wbflush();
wbuf[widx++] = c;
}
void writeInt(int n) {
int isz = unitSize(n);
if (isz + widx >= WBUF_SIZE) wbflush();
if (n < 0) {
wbuf[widx++] = '-';
n = -n;
}
int next = widx + isz;
while (isz--) {
wbuf[widx + isz] = n % 10 + '0';
n /= 10;
}
widx = next;
write('\n'); // 구분자
}
//----------------------------------------------------------
#define SIZE 1024
int num[SIZE+1][SIZE+1];
int main(){
int N, M, a;
N = readInt();
M = readInt();
for( int i = 1; i <= N; i++){
for( int j = 1; j <= N; j++){
a = readInt();
num[i][j] = num[i][j-1] + num[i-1][j] - num[i-1][j-1] + a;
}
}
int sum, x1, y1, x2, y2;
for( int i = 0; i < M; i++){
x1 = readInt();
y1 = readInt();
x2 = readInt();
y2 = readInt();
sum = num[x2][y2] - num[x2][y1-1] - num[x1-1][y2] + num[x1-1][y1-1];
writeInt(sum);
}
wbflush();
return 0;
}
'문제 풀이 > 백준 (BOJ)' 카테고리의 다른 글
[백준/BOJ] 1629번: 곱셈 ( 분할 정복법 ) - C++ 문제 풀이 (0) | 2024.05.24 |
---|---|
[백준/BOJ] 1931번: 회의실 배정 - C++ 문제 풀이 (0) | 2024.05.22 |
[백준/BOJ] 11659번: 구간 합 구하기 4 ( 동적 계획법 ) - C++ 문제 풀이 (0) | 2024.05.17 |
[백준/BOJ] 14889번: 스타트와 링크 (백트래킹 기법) - C++ 문제풀이 (0) | 2024.05.15 |
[백준/BOJ] 15649번, 15651번: N과 M (백트래킹 기법) - C++ 문제 풀이 (0) | 2024.05.11 |