백준 11660 - 구간 합 구하기 5

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

11660번: 구간 합 구하기 5

구간 합 구하기 4에서 사용했던 수열의 부분합 공식 Ai + A(i+1) + ... + Aj = Sj - S(i-1)을 떠올려보자. 이 공식을 2차원으로 확장할 수 있다면 해결할 수 있는 문제다.

 

다음 그림을 보자.

계산할 구간이 입력으로 3, 3, 4, 4가 들어왔다. 위의 색칠한 부분이 이에 해당한다. 이 부분을, 맨 왼쪽 위의 점을 하나의 꼭지점으로 갖는 직사각형을 통해 나타낼 수 있을까? 예를 들면....

짜잔. (4)는 (2)와 (3)에서 겹치는 부분으로, 두 번 뺄셈되었으므로 다시 한 번 더해줬다.

 

그래서 이 직사각형들을 어디에 써먹는가? 여기까지 떠올리면 바로 문제를 풀러가면 된다.

입력받은 표와 동일한 크기의 2차원 배열 sum을 생성해보자. 그리고 sum[i][j]의 값을 맨 왼쪽 위 점(1,1)에서 시작해 점 (i,j)에서 끝나는 직사각형에 포함되는 원소들의 합이라고 해보자. 위의 예시를 sum[i][j]로 나타내면 다음과 같다.

 

문제 해결의 실마리가 모두 주어졌다..... 남은 것은 동적 계획법을 이용해 sum 배열의 값을 채우는 것 뿐이다.

 

주요 코드

int main(){

    //setup
    for (int i = 1; i <= size; i++) {
        sum[1][i] = sum[1][i - 1] + v[1][i];
        sum[i][1] = sum[i - 1][1] + v[i][1];
    }

    //fill
    for (int i = 1; i <= size; i++)
        for (int j = 1; j <= size; j++)
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + v[i][j];
}

int getIntervalSum(Matrix& sum, int x1, int y1, int x2, int y2) {
	return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
}