2차원 누적 합 배열 만들기 5-2 C++(1493)[코드업, code up]

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

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

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

문제 주소입니다.

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

[기초-배열연습] 2차원 누적 합 배열 만들기 5-2

---

1. 문제

2. 문제 해석

3. 소스 코드

---

문제

n*m개의 데이터를 배열에 입력 받은 후, (1, 1) 데이터 ~ (n, m) 영역의 누적 합 배열을 만들고 출력해보자. 3*5개의 데이터가 다음과 같이 입력되었을 때, 1 2 3 4 5 5 4 3 2 1 1 5 2 4 3 아래와 같이 출력하면 된다. 1 3 6 10 15 6 12 18 24 30 7 18 26 36 45 k번째 위치에 저장되어야 하는 값의 관계식은 어떻게 표현할 수 있을까? s[i][j] = ?

입력

첫 번째 줄에 배열의 크기 n, m이 공백을 두고 입력된다. 두 번째 줄부터 m개의 데이터가 공백을 두고 n줄로 입력된다. [입력값의 정의역] 1<= n, m <= 100 -1000 <= k <= 1000

출력

n*m 개의 2차원 누적 합 데이터를 한 줄로 출력한다

입력 예시

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

출력 예시

1 3 6 10 15 6 12 18 24 30 7 18 26 36 45

---

2. 문제풀이

이 문제에서 중요한 부분은 중복되서 더 하지 않는 부분입니다. 1,1을 계산할때 저는 간단하게 계산이 완료된 (1,0)과 (0, 1) 그리고 계산이 되지않은 (1,1)을 더해서 만들어보려 했습니다. 그랬더니 0,0 부분이 겹쳐서 따로 빼줘야 하더군요.   그래서 계산을 쉽게하기 위해 원본배열과 계산후 배열을 따로만들기로 했습니다. ex) 1,1 이라면 (0, 0), (0, 1), (1, 0), (1, 1)을 더해줘야 합니다.   이렇게 계산하기 위해서는 4중 for문을 사용해야 했습니다. 나중에 좀더 효율적으로 더할 수 있는 방법을 찾는다면 수정하도록 하겠습니다.

---

3. 소스코드

#include <iostream>
 
using namespace std;
 
int main() {
    int n, m, temp, arr[100][100]{ 0 }, arr2[100][100]{ 0 };
    cin >> n >> m;
    //기본배열에 값을 입력받는다.
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
        }
    }
    //두번째 배열에 이전까지 있던 합들을 더한다.
    //ex) 1,1 이라면 (0, 0), (0, 1), (1, 0), (1, 1)을 더해준다.
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = 0; k <= i; k++) {
                for (int z = 0; z <= j; z++) {
                    arr2[i][j] += arr[k][z];
                }
            }
        }
    }
    //더한 값들을 출력
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << arr2[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}