[코드업] 2차원 차이 배열 만들기 5-4 문제풀이(C++)

greedy하게 해결하면 해결완료 / 누적합은 가로 따로, 세로 따로 구해주어야 함  + 세그멘테이션 오류 조심

 

 

    #include<iostream>
    #include<vector>
    using namespace std;
 
    /*
    <문제>
    크기 n*m인 2차원배열 d[][]에서
    k개의 구간(x1, y1, x2, y2)와 u를 받아서
    d[x1][y1] += u
    d[x2+1][y2+1] += u
    d[x1][y2+1] -= u
    d[x2+1][y1] -= u
    수행 후, 누적합을 만들어서 출력
 
    <입력>
    n m k
    k개의 데이터 공백두고 출력(x1, y1, x2, y2, u)
    [입력값의 정의역]
    1 <= n, m <=1000
    1 <= k <= 700
    1 <= x1 <= x2 <= n
    1 <= y1 <= y2 <= m
    -1000 <= u <= 1000
 
    <출력>
    n*m배열 상태를 출력 후,
    줄 바꿔서 2차원 누적합 계산해서 출력
    */
    int main() {
        int n, m, k; cin >> n >> m >> k;
        int d[1001][1001];    //n*m 배열 생성
 
        for (int i = 0; i < k; i++) {    //k번 반복
            int x1, y1, x2, y2, u; cin >> x1 >> y1 >> x2 >> y2 >> u;
            d[x1][y1] += u;
            d[x2 + 1][y2 + 1] += u;
            d[x1][y2 + 1] -= u;
            d[x2 + 1][y1] -= u;
        }
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cout << d[i][j] << " ";
            }
            cout << endl;
        }
        cout << endl;
        for (int j = 0; j < m; j++)
            for (int i = 0; i < n; i++)
                if (i + 1 < n) d[i + 1][j] += d[i][j];
 
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (j + 1 < m) d[i][j + 1] += d[i][j];
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cout << d[i][j] << " ";
            }
            cout << endl;
        }
        return 0;
    }