Beakjoon] 구간 합 구하기 5 (백준 코테) = 구간합

하 정말 얼마만에 쓰는 알고리즘, 코딩테스트 탭인지...
해커랭크 풀다가 영어문제 읽는거에서부터 지쳐서 포기하고.. 파이썬 책사서 책에 있는 문제 풀다가....
일이 바빠서 놨다가.. 다시 C++로 된 책 사서 공부하다 넘 어려워서 서점가서 직접 보고 고른책 덕에 다시 백준으로 시작..
책은 다음에 리뷰하기로..

---

문제주소 : https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

문제 :  2차원배열의 표에서 (x1, y1) 위치부터 (x2, y2)까지 포함되는 모든 값을 더하는것

 

풀이 : 범위값은 쌩으로 매번 각 쉘의 값을 가져와서 구할 수 있으나 시간복잡도가 O(n^2)임 보통 제한시간에서 아웃되게 된다.

그래서 구간의 합을 여러번 구해야 하는경우엔 구간 합을 미리 구해놓고 범위에 따라 덧셈 뺄샘만 조금 해주면 n(1)의 속도로 동작이 가능하다

 

 

코드는 아래 숨김

코드

#include <iostream>
#include <vector>


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

    int n, m; //표의 크기, 구할 합의 수
    std::cin >> n >> m;
    
    //원본 이차원 배열
    std::vector<std::vector<int>> ori_array(n + 1, std::vector<int>(n + 1, 0));
    //구간 합 계산용 
    std::vector<std::vector<int>> sum_array(n + 1, std::vector<int>(n + 1, 0));
    
    //구간합 계산 
    for (int i = 1; i < n+1; ++i) {
        for (int j = 1; j < n+1; ++j) {
            std::cin >> ori_array[i][j];
            sum_array[i][j] = sum_array[i - 1][j] + sum_array[i][j - 1] - sum_array[i-1][j-1] + ori_array[i][j];
        }
    }

    std::vector<int> result;

    //구간으로 값 추출
    int x1, y1, x2, y2;
    for (int i = 0; i < m; ++i) {
        std::cin >> x1 >> y1 >> x2 >> y2;
        result.push_back(sum_array[x2][y2] - sum_array[x2][y1-1] - sum_array[x1-1][y2] + sum_array[x1-1][y1-1]);
    }
    
    //출력
    for (auto iter = result.begin(); iter != result.end(); ++iter) {
        std::cout << *iter << "\n";
    }


    
    return 0;

}

 

알게 된 것 : 반복되는 구간합은 무조건 누적 구간합을 구해두는것이 낫다

1차원값의 경우 누적합을 arr에 저장하였다면

어느 시작점으로부터 종료지점까지의 값은 "arr[종료] - arr[시작-1]" 으로 구할 수 있고

2차원값의 경우엔 "arr[종료x][종료y] - arr[종료x-1][시작x] - arr[시작x-1][종료y] + arr[시작-1][종료-1]" 로 구할 수 있다

코드로 보는게 이해가 빠를듯... 글로 쓰니 더 어렵네.. 다시 화이팅

---