2차원 차이 배열 만들기 5-4 C++(1495)[코드업, Code up]

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀 더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소입니다.

https://codeup.kr/problem.php?id=1495

[기초-배열연습] 2차원 차이 배열 만들기 5-4

---

1. 문제

2. 문제 해석

3. 소스 코드

---

문제

크기가 n*m인 2차원 배열 d[][]에 대해 k개의 구간 [(x1, y1), (x2, y2)] 과 u를 입력 받아, d[x1][y1] = d[x1][y1]+u; d[x2+1][y2+1] = d[x2+1][y2+1]+u; d[x1][y2+1] = d[x1][y2+1]-u; d[x2+1][y1] = d[x2+1][y1]-u; 를 수행한 후, 누적 합을 만들어 출력해보자. 크기가 7*7이고, 4개의 구간 데이터 1 1 2 2 1 2 2 3 3 1 3 3 4 4 1 4 4 5 5 1 가 입력되면 2차원 배열의 상태는 0 0 0 0 0 0 0 0 1 0 –1 0 0 0 0 0 1 0 –1 0 0 0 –1 0 2 0 –1 0 0 0 –1 0 2 0 -1 0 0 0 -1 0 1 0 0 0 0 0 -1 0 1 가 되며 그 누적합을 계산하면 아래와 같다. 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 2 1 0 0 0 0 0 1 2 1 0 0 0 0 0 1 2 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0

 

입력

첫 번째 줄에 배열의 크기 n, m과 구간의 개수 k가 공백을 두고 입력된다. 두 번째 줄부터 k개의 데이터가 공백을 두고 입력된다. [입력값의 정의역] 1 <= n, m <=1000 1 <= k <= 700 1 <= x1 <= x2 <= n 1 <= y1 <= y2 <= m -1000 <= u <= 1000

출력

n*m 배열의 상태를 출력한 후, 줄을 바꿔 2차원 누적합을 계산해 출력한다.

입력 예시

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

출력 예시

0 0 0 0 0 0 0  0 1 0 -1 0 0 0  0 0 1 0 -1 0 0  0 -1 0 2 0 -1 0  0 0 -1 0 2 0 -1  0 0 0 -1 0 1 0  0 0 0 0 -1 0 1  0 0 0 0 0 0 0  0 1 1 0 0 0 0  0 1 2 1 0 0 0  0 0 1 2 1 0 0  0 0 0 1 2 1 0  0 0 0 0 1 1 0  0 0 0 0 0 0 0

2. 문제풀이

---

조금뒤에 작성하도록 하겠습니다.

---

3. 소스코드

#include <iostream>
 
using namespace std;
 
int main() {
    int k, n, d[1001][1001]{ 0 }, arr[1001][1001]{ 0 }, x1, x2, y1, y2, u, m;
    cin >> k >> m >> n;
    //n개만큼의 데이터가 들어온다
    //공식대로 처리한다.
    for (int i = 0; i < n; i++) {
        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 < k; i++) {
        for (int j = 0; j < m; j++) {
            cout << d[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
    //시간을 단축하기 위해 조건문 사용
    //자신의 왼쪽과 위를 더한거에 i-1 j-1을 빼면 중복된 부분이 제거가 된다.
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < m; j++) {
            if (!i && !j)    arr[i][j] = d[i][j];
            else if (!i)    arr[i][j] = arr[i][j - 1] + d[i][j];
            else if (!j)    arr[i][j] = arr[i - 1][j] + d[i][j];
            else    arr[i][j] = arr[i][j - 1] + arr[i - 1][j] - arr[i - 1][j - 1] + d[i][j];
            cout << arr[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}