구간 합 문제

이 문제들은 사실 그렇게 어렵지는 않다. 근데 대부분 시시간제한에 걸린다. 따라서 그냥 푸는걸 넘어서 빠르게 푸는게 필요하다.

1차원 배열 구간합

arr= [1, 2, 3, 4, 5]가 있다고 하자.
이를 입력받으면서 동시에 이전자리수까지의 합을 전부 더해준다.

그러면 sum = [1, 3, 6, 10, 15]가 될 것이다.

그리고 나서는 정해진 구간, 예를 들어 2부터 4까지면,
sum[4] - sum[1]을 하면 된다

2 + 3 + 4 = 9 / 10 - 1 = 9

아주 표본적인 문제가 백준 11659번이다.

11659번 풀이

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

int n, m, val;
int a, b, sum;


int main() {
    cin >> n >> m;
    int arr[n+1];
    int sum[n+1];
    int ans[m];
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        sum[i] = sum[i - 1] + arr[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        int temp = sum[b] - sum[a-1];
        ans[i] = temp;
    }
    for(int i = 0; i < m; i++) {
        cout << ans[i] << "\n";
    }
    
}

풀이설명은 딱히 필요없을것 같다.

2차원 배열

2차원 배열도 1차원과 똑같은 방식으로 처리해야하는데, 조금 더 복잡하다.

일단 시간신경쓰지 않고 그냥 푸는 방식이다.

그냥 풀기

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

struct point {
    int x1;
    int y1;
    int x2;
    int y2;
};

int n, m;
int arr[1025][1025];
vector <point> vec;

int main() {
    cin >> n >> m;
    int ans[m];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
        }
    }
    int x1, y1, x2, y2;

    for (int i = 0; i < m; i++) {
        point p1;
        cin >> p1.x1>> p1.y1 >> p1.x2 >> p1.y2;
        vec.push_back(p1);
    }
    for (int i = 0; i < m; i++) {
        int sum = 0;
        x1 = vec[i].x1;
        y1 = vec[i].y1;
        x2 = vec[i].x2;
        y2 = vec[i].y2;

        for (int x = x1; x <= x2; x++) {
            for (int y = y1; y <= y2; y++) {
                sum += arr[x][y];
            }
        }
        ans[i] = sum;
    }
    
    for(int elem : ans) {
        cout << elem << "\n";
    }
}

O(1) 시간만에 풀기

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

int n, m;
int arr[1025][1025];

int main() {
    cin >> n >> m;
    int ans[m];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            arr[i][j] += arr[i-1][j];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            arr[i][j] += arr[i][j-1];
        }
    }
    int x1, y1, x2, y2;

    for (int i = 0; i < m; i++) {
        int sum = 0;
        cin >> x1 >> y1 >> x2 >> y2;
        sum = arr[x2][y2]-arr[x1-1][y2]-arr[x2][y1-1]+arr[x1-1][y1-1];
        ans[i] = sum;
    }
    for (int elem : ans) cout << elem << "\n";
}

2차원 배열이기에, 구간합을 구할 때, x축, y축 모두 신경을 써서 합해줘야한다.

그리고 마지막에 차를 구할 떄 역시 x-1, y-1을 빼야한다. 이때 x-1,y-1은 겹쳐져서 두번 빠지기 때문에 이를 더해줘야한다.