[ 백준 11660 ] 구간 합 구하기 5 (C++) - 누적 합

---

🔗 문제 링크

11660번: 구간 합 구하기 5

---

💡 문제 풀이 및 해석

1. 누적합 문제로써 매번 계산하면 안 되는 문제다.
2. 이미 누적이 된 상태에서 상수시간으로 각각의 케이스를 해결해야 한다.
3. 수학적으로 부분구역은 acc [ey][ex] + acc [sy - 1][sx - 1] - acc[sy - 1][ex] - acc [ey][sx - 1] 이미 누적된 데이터만 있으면 상수 시간 안에 해결이 가능하다.
4. 누적된 데이터는 acc [y][x]=myMap [y][x]+acc [y-1][x]+acc [y][x-1]-acc [y-1][x-1]으로 현재값에서 누적된 위아래 값을 더해주고, 왼쪽 위의 누적값을 빼주면 누적된 데이터가 나온다.

---

⭐️ 정답 코드 및 설명

#include <iostream>

using namespace std;

int N, M, sx, sy, ex, ey;
int myMap[1025][1025];
int acc[1025][1025];

void accMap(int x, int y){
    acc[y][x]=myMap[y][x]+acc[y-1][x]+acc[y][x-1]-acc[y-1][x-1];
}

void makeAccMap(){
    for(int y = 1; y <= N; y++){
        for(int x = 1; x <= N; x++){
            accMap(x, y);
        }
    }
}

void input(){
    ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
    cin >> N >> M;
    for(int y = 1; y <= N; y++){
        for(int x = 1; x <= N; x++){
            cin >> myMap[y][x];
        }
    }
    makeAccMap();
}

int main() {

    input();
    for(int i = 0; i < M; i++){
        cin >> sy >> sx >> ey >> ex;
        cout << acc[ey][ex] + acc[sy - 1][sx - 1] - acc[sy - 1][ex] - acc[ey][sx - 1]  << "\n";
    }

    return 0;
}

---

🤔 문제 후기

누적합으로 문제를 풀라고 대놓고 되어 있었는데, 실제로 수학적인 배경 지식이 있다면 어렵지 않은 문제였다.