[백준] 2167번 : 2차원 배열의 합 - C/C++

 

문제 해결 과정은 아래와 같다.

1. 배열 입력

2. 합을 구할 K 입력 받고 정수 네 개 입력 받기

3. 합 구하기

 

 

벡터를 이용하여 동적으로 2차원 배열을 생성할 것이다.

vector<vector<int>> ary(n + 1, vector<int>(m + 1, 0));

 

• ary[n+1][m+1] → (1-based index)로 사용하기 위해 입력받은 n,m을 각각 1씩 증가시킨다
• 누적합 계산을 쉽게 하기 위해서 모든 값을 0으로 초기화 시킨다.

 

-2차원 누적합(prefix sum)???

수들의 나열에서 특정 구간의 합을 의미하는 prefix sum은

보통은 1차원 배열에서 i부터 k 인덱스 사이의 값을 구하는 데에 이용된다.

 

부분합은 아래와 같이 코드를 작성할 수 있다.

for (int i = 1; i <= n; i++) {
   for (int j = 1; j <= m; j++) {
      int num;
      cin >> num;
      ary[i][j] = num + ary[i - 1][j] + ary[i][j - 1] - ary[i - 1][j - 1];
    }
}

 

 

위의 코드를 분석해보자.

 

• 기존 배열을 입력받는 동시에 누적합 저장
• ary[i][j]는 (1,1)부터 (i,j)까지의 부분합을 의미
• 공식: ary[i][j]=num+ary[i−1][j]+ary[i][j−1]−ary[i−1][j−1] 
  • num: 현재 입력받은 숫자
  • ary[i-1][j]: 바로 위쪽 누적합
  • ary[i][j-1]: 바로 왼쪽 누적합
  • ary[i-1][j-1]: 위쪽과 왼쪽에서 중복된 부분 제거
    → ary[i-1][j]와 ary[i][j-1]을 더할 때 (i-1, j-1)을 두 번 연산 했기 때문에
    중복된 연산은 제거해주어야 함

 

2차원 누적합(prefix sum)을 구했으니,

이제 부분합을 구해보자.

for (int i = 0; i < k; i++) {
    int i1, j1, x, y;
    cin >> i1 >> j1 >> x >> y;
    int sum = ary[x][y] - ary[i1 - 1][y] - ary[x][j1 - 1] + ary[i1 - 1][j1 - 1];
    cout << sum << '\n';
}

• (i1, j1)부터 (x, y)까지의 합을 빠르게 구하는 공식
  : sum=ary[x][y]−ary[i1−1][y]−ary[x][j1−1]+ary[i1−1][j1−1]
• ary[x][y]: (1,1)부터 (x,y)까지의 전체 합
• ary[i1-1][y]: 위쪽 범위 제외
• ary[x][j1-1]: 왼쪽 범위 제외
• ary[i1-1][j1-1]: 두 번 제외된 부분 한번 더하기

 

 

 

전체 코드

#include <iostream>
#include <vector>

//2차원 배열의 합
using namespace std;

int main(){
    int n,m,k;
    cin >> n >> m;

    //누적합 개념 이용
    //int ary[n+1][m+1] = {0};
    // 2d vector 이용 (0으로 초기화)
    vector<vector<int>> ary(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int num;
            cin >> num;
            ary[i][j] = num + ary[i - 1][j] + ary[i][j - 1] - ary[i - 1][j - 1];
        }
    }

    cin >> k;

    for (int i = 0; i < k; i++) {
        int i1, j1, x, y;
        cin >> i1 >> j1 >> x >> y;
        int sum = ary[x][y] - ary[i1 - 1][y] - ary[x][j1 - 1] + ary[i1 - 1][j1 - 1];
        cout << sum << '\n';
    }
    return 0;
}

 

 

실버5의 어려운 문제였다.

처음 문제를 접했을 때 어떻게 풀어야할지 감이 안 잡혀서

문제 하단에 적혀있는 '알고리즘 분류'를 참고했다.

누적합은 한번 배웠던 개념이지만 아직은 낯설다.

더 연습을 많이해서 익숙해지도록 해야겠다.

 

 

 

 

 

더 좋은 풀이가 있다면 댓글로 알려주세요 !!

피드백 환영입니다☺️