[백준 2167 c++ O] 2차원 배열의 합

- 풀이 원본: https://github.com/xhaktmchl/Algorithm_study/blob/main/BOJ/%EB%88%84%EC%A0%81%ED%95%A9/%5B%EB%B0%B1%EC%A4%80%202167%20c%2B%2B%20O%5D%202%EC%B0%A8%EC%9B%90%20%EB%B0%B0%EC%97%B4%EC%9D%98%20%ED%95%A9.cpp

GitHub - xhaktmchl/Algorithm_study: 알고리즘 이론 및 문제풀이

 

#include <iostream>
#include <algorithm>
using namespace std;
/*
[백준 2167 c++ O] 2차원 배열의 합
문제:
접근1: 완탐 -> 시간 초과 
접근2: 행 마다 누적합 저장해놓으면 -> 배열의 구간 합 계산 가능
풀이: 
    //1.입력
    //배열
    //범위
    //2.행 누적합 구하기
    //3.각 구간의 배열 합 구하기
    //4.출력: 구간 합
*/
int n, m, k,xs,ys,xe,ye;
int a[310][310];
int pSum[310][310];

int calSum() {
    
    //i,j까지 구간합
    int sum1 = 0, sum2 = 0;
    /*for (int i = 1; i <= y1; i++) {
        sum1 += pSum[i][x1] - pSum[i][0];
    }*/
    //x,y까지 구간합
    for (int i = ys; i <= ye; i++) {
        sum2 += pSum[i][xe] - pSum[i][xs - 1];
        //cout << sum2 << '\n';
    }
    //두개의 차 + (i,j)원소 합
    return sum2;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    //1.입력
    //배열
    //범위
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            //2.행 누적합 구하기
            pSum[i][j] = pSum[i][j - 1] + a[i][j];
        }
    }
    
    //3.각 구간의 배열 합 구하기
    cin >> k;
    for (int  i = 0; i < k; i++) {
        cin >> ys >> xs >> ye >> xe;
        //4.출력: 구간 합
        cout << calSum() << '\n';
    }
}

 

- 풀이2 :

https://github.com/xhaktmchl/Algorithm_study/blob/main/BOJ/%EB%88%84%EC%A0%81%ED%95%A9/%5B%EB%B0%B1%EC%A4%80%202167%20c%2B%2B%20OO%5D%202%EC%B0%A8%EC%9B%90%20%EB%B0%B0%EC%97%B4%EC%9D%98%20%ED%95%A9.cpp

GitHub - xhaktmchl/Algorithm_study: 알고리즘 이론 및 문제풀이

#include <iostream>
#include <algorithm>
using namespace std;
/*
[백준 2167 c++ OO] 2차원 배열의 합
문제:
접근1: 완탐 -> 시간 초과
접근2: 행 마다 누적합 저장해놓으면 -> 배열의 구간 합 계산 가능
시간복잡도: 
풀이:
    //1.입력
    //배열
    //범위
    //2.행 누적합 구하기
    //3.각 구간의 배열 합 구하기
    //4.출력: 구간 합
풀이2: 
//pSum =누적합
sum(2,2~4,4) = pSum[4][4] -pSum[4][1] -pSum[1][4] + pSum[1][1]
*/
int n, m, k, xs, ys, xe, ye;
int a[310][310];
int pSum[310][310];

int calSum() {

    //i,j까지 구간합
    int sum = 0;
    //x,y까지 구간합
    for (int i = ys; i <= ye; i++) {
        sum += pSum[i][xe] - pSum[i][xs - 1];
    }
    //두개의 차 + (i,j)원소 합
    return sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    //1.입력
    //배열
    //범위
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            // 누적합
            pSum[i][j] = a[i][j]+ pSum[i][j - 1] + pSum[i - 1][j] - pSum[i - 1][j - 1];
        }
    }

    //3.각 구간의 배열 합 구하기
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> ys >> xs >> ye >> xe;
        //4.출력: 구간 합
        cout << pSum[ye][xe] - pSum[ys-1][xe] - pSum[ye][xs-1] + pSum[ys-1][xs-1] << '\n';
    }
}