[ 백준 17123 ] 배열 놀이 (c/c++)

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

 

 

[ 문제 요약 ]

 (r1, c1, r2, c2, v)가 주어지는데, 이 연산은 (r1, c1)부터 (r2, c2)까지 사각형 영역에 속한 A[r, c]의 값을 v만큼 더하는 것일 때, N개의 정수로 표현된 각 행의 합과 열의 합을을 공백으로 구분하여 출력한다.

 

 

[ 문제 풀이 ]

1. 누적합을 이용해서 최대한 반복을 적게 해야 한다.

2.  (r1, c1, r2, c2, v)가 주어지면 diff[r1][c1] += v, diff[r1][c2 + 1] -= v, diff[r2 + 1][c1] -= v, diff[r2 + 1][c2 + 1] += v 를 통해 사각형 내부의 합이 증가하도록 한다.

3. 연산 과정이 끝나면  배열의 수를 계산한다.

4. 각 열과 행의 합을 출력한다.

 

 

[ 소스 코드 ]

#include <bits/stdc++.h>
using namespace std;

int t, N, M;
int sum, r1, c1, r2, c2, v;
int arr[1010][1010], diff[1010][1010];

int main() {
    cin >> t;
    while (t--){
        cin >> N >> M;
        memset(arr, 0, sizeof(arr));
        memset(diff, 0, sizeof(diff));
        for (int i=1; i<=N; i++) for (int j=1; j<=N; j++)
            cin >> arr[i][j];
        
        while (M--){
            cin >> r1 >> c1 >> r2 >> c2 >> v;

            diff[r1][c1] += v;
            diff[r1][c2 + 1] -= v;
            diff[r2 + 1][c1] -= v;
            diff[r2 + 1][c2 + 1] += v;   
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
                arr[i][j] += diff[i][j];
            }
        }
        
        for (int i=1; i<=N; i++){
            sum = 0;
            for (int j=1; j<=N; j++) sum += arr[i][j];
            cout << sum << " ";
        }
        cout << "\n";
        
        for (int i=1; i<=N; i++){
            sum = 0;
            for (int j=1; j<=N; j++) sum += arr[j][i];
            cout << sum << " ";
        }
        cout << "\n";
    }
    return 0;
}

 

 

 

[ 주의할 점 ]

누적합의 개념을 이해하고 시간이 부족하다는 것을 알면 풀 수 있는 문제였다.