백준 11660 - 구간 합 구하기 5

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

 

풀이과정

NxN 표에서 일정 구간의 합을 구하는 문제이다.

(y1, x1)부터 (y2, x2)까지의 합을 구하면 된다.

 

시간복잡도

0. N은 최대 1024이며, 구해야 하는 횟수 M은 최대 100,000 이다.

만약 배열을 그대로 입력받아서 100,000번 연산을 하게 되면, 시간복잡도 O(N^2*M) 으로 시간제한 1초 안에 해결할 수 없다.

 

풀이

1. 값을 입력받을때 마다 그 지점까지의 연산 결과를 저장해놓아야 한다.

점화식으로 표현하면 아래와 같다.

dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + num

dp[i][j] 는 table[0][0] ~ table[i][j] 까지의 합 을 의미한다.

 

2. dp 테이블에 모든 결과를 저장해놓았다면, 특정 구간에서의 합을 구할 때 계산식은 아래와 같다.

dp[y2][x2] - dp[y1-1][x2] - dp[y2][x1-1] + dp[y1-1][x1-1]

 

2-1. 예를들어 (2,2) ~ (3,4) 까지의 합을 구한다고 하면, (3,4) 에서 불필요한 부분들을 제거하면 된다.

(2,2) 를 기준으로 모든 계산을 하면 되는데, y축으로 -1, x축으로 -1 만큼의 부분들이 필요가 없기 때문에

dp[1][4] 와 dp[3][3] 을 빼주면 되는것이다. 다만 dp[2-1][2-1] 은 두번 계산되기 때문에 마지막에 한번 더해준다.

 

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

 

코드

#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <cstring>
using namespace std;

int dp[1025][1025];

void solution(int y1, int x1, int y2, int x2) {
    printf("%d\n",dp[y2][x2] - dp[y1-1][x2] - dp[y2][x1-1] + dp[y1-1][x1-1]);
}

int main() {
    int N,M,num;
    int y1,x1,y2,x2;
    scanf("%d %d",&N,&M);

    for(int i=1; i<=N; i++) {
        for(int j=1; j<=N; j++) {
            scanf("%d",&num);
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + num;
        }
    }
    for(int i=0; i<M; i++) {
        scanf("%d %d %d %d",&y1,&x1,&y2,&x2);
        solution(y1,x1,y2,x2);
    }
}