[백준][C++] 11660: 구간 합 구하기 5

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

11660번: 구간 합 구하기 5

 

 

 

 

---

- 문제

 

  2차원 배열상의 표가 주어지면 (x1,y1)부터 (x2,y2)까지의 합을 구하는 문제다.

 

 

---

- 해설

구간 합 구하기 4까지는 일차원 배열 문제라 쉬웠는데, 이것도 이차원 배열이라는 거 빼고는 다를 게 없다.

 

가장 먼저 값을 어떻게 넣어줄건지를 생각해야 한다.

 

 

 

(가로로 먼저 더하고 세로로 더하는 방법을 사용했다.)

 

1 2 3 4

2 3 4 5

3 4 5 6

4 5 6 7

 

1. 이 있으면 먼저 가로로 더해서

 

1 3 6 10

2 5 9 14

3 7 12 18

4 9 15 22

 

2. 이렇게 만들고 세로로 더해서

 

1 3 6 10

3 8 15 24

6 15 27 42

10 24 42 64

 

이렇게 만들었다.

 

마지막으로

 

3. (4,4)에서 (4,4)까지의 합을 구하려고 하면

 

(4,4) - (4-1,4) - (4,4-1) + (4-1,4-1) == (4,4) - (3,4) - (4,3) + (3,3)을 하면 정답이 나온다.

64 - 42 - 42 + 27 = 7

 

비슷하게 (2,3)에서 (4,4)까지의 합을 구하려고 하면

(4,4) - (2-1,4) - (4,3-1) + (2-1,3-1) == (4,4) - (1,4) - (4,2) + (1,2)

64 - 10 - 9 + 3 = 48

 

이런 식으로 풀 수 있다.

 

 

---

- 풀이

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M, x1, y1, x2, y2, temp;
    cin >> N >> M;
    vector<int> vX(1025, 0);
    vector<vector<int>> vBoard(1025, vX); // 이차원 배열에 저장해야 함

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            cin >> temp;
            vBoard[i][j] = temp + vBoard[i][j - 1]; // 1. 가로로 증가함에 따라 더해준다( 1 2 3 4 ) 이렇게 있으면 ( 1 3 6 10) 이렇게 저장
        }
    }
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            vBoard[i][j] += vBoard[i - 1][j]; // 2. 세로로 증감하에 따라 더함(가로로는 이미 더했으니 그 위에 값과 현재 값만 저장하면 됨)
        }
    }
    for (int i = 1; i <= M; i++)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        cout << vBoard[x2][y2] - vBoard[x2][y1 - 1] - vBoard[x1 - 1][y2] + vBoard[x1 - 1][y1 - 1] << '\n'; // 3. 현재 - 좌측 값 - 위에 값 + 좌상값 = 정답
    }

    return 0;
}

 

 

---

- 새롭게 알게 된 점