[백준/BOJ] 11660번: 구간 합 구하기 5 ( 동적 계획법 ) - C++ 문제풀이

 

문제 설명

 

문제 링크: https://www.acmicpc.net/problem/11660

 

풀이

이 문제는 이차원 배열의 부분 구간 합을 구하는 문제입니다.

 

짐작한 바와 같이, 단순히 (x1, y1) ~ (x2, y2) 구간의 값들을 합해서 답을 제시하면 시간제한에 걸립니다.

그래서 구하려고 하는 부분 구간의 합을, 계산하기 쉽고 빠른 전체 구간의 합에서 더 작은 구간의 합을 빼는 방식으로 문제를 풀려고 합니다.

 

전체 구간의 합은 더 작은 구간의 합으로 만들 수 있고, 그 작은 구간의 합을 저장해 뒀다면 빠르게 합을 구할 수 있습니다.

이렇듯, 동적 계획법이란 전체의 문제를 작은 부분 문제로 나누어 계산한 후, 이 계산의 결과를 사용하여 전체의 문제를 빠르게 푸는 방법입니다.

 

S(x, y)를 배열 처음부터 (x, y)까지 구간의 합이라고 하면,

S(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;
}