구간 합 구하기

오늘은 구간 합에 관련된 문제 두 개를 한 번에 풀면서 풀이 과정을 공유해보려고 한다. 단계별로 11659 -> 11660 순서로 풀이를 진행해보려고 한다. 우선 구간 합을 고민할 때 고려해야할 점은 시간초과가 되기 매우 쉽다는 것이다. 만약 매번 구간의 합을 구하려고 한다면 연산량이 매우 많이 늘어날 것이므로 처음부터 S[i]를 받는다는 생각으로 받는 것이 매우 중요하다. 아래 코드를 보면 cin으로 받는 과정에서 이전값과의 합으로 받게 되는데 이 과정이 구간합을 미리 받은 후 계산을 하는 경우에는 그냥 차만 활용해서 계산한다고 보면된다.

#include "iostream"
using namespace std;
#define MAX_SIZE 100001

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int arr[MAX_SIZE], N, M;
    cin >> N >> M;
    cin >> arr[0];
    for (int i = 1; i < N; i++){
        cin >> arr[i];
        arr[i] = arr[i] + arr[i - 1];
    }
    for (int i = 0; i < M; i++){
        int temp1, temp2;
        cin >> temp1 >> temp2;
        if (temp1 > 1)
            cout << arr[temp2 - 1] - arr[temp1 - 2] << "\n";
        else cout << arr[temp2 - 1] << "\n";

    }

}

위에서 활용한 구간 합을 토대로 2차원 배열에서도 이를 활용해보자. 최대한 이전 코드를 활용하기 위해 별의별 짓을 다했는데 그러다 보니 틀렸습니다를 두 번이나 맞게 되었다. 이 문제는 각 열별로 합을 따로 구해야하는데 0행들은 앞 행이 없다보니 이에 대해서 예외 처리를 계속해서 해줘야했다. 그렇다보니 예외 처리를 여러번 반복해서 해줘야했고, 위의 코드처럼 한 두 줄 깔짝이는걸로는 오류가 안잡혀서 여러 번의 시행착오를 겪게 되었다. 엥간하면 0행은 다 0으로 넣은 다음에 1행부터 계산을 시작하는게 신상에 더 좋을 듯 하다.

#include <iostream>
using namespace std;

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

    int ans[1024][1024] = {0,}, N, M;
    cin >> N >> M;
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            cin >> ans[i][j];
        }
    }
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            if (i == 0 && j == 0)
                ans[i][j] = ans[i][j];
            else if (i == 0)
                ans[i][j] = ans[i][j - 1] + ans[i][j];
            else if (j == 0)
                ans[i][j] = ans[i - 1][j] + ans[i][j];
            else
                ans[i][j] = ans[i][j - 1] + ans[i - 1][j] - ans[i - 1][j - 1] + ans[i][j];
        }
    }
    for (int i = 0; i < M; i++){
        int temp1x, temp1y, temp2x, temp2y;
        cin >> temp1x >> temp1y >> temp2x >> temp2y;
        if (temp1x == 1 && temp1y == 1 )
            cout << ans[temp2x - 1][temp2y - 1] << "\n";
        else if (temp1x == 1)
            cout << ans[temp2x - 1][temp2y - 1] - ans[temp2x - 1][temp1y - 2]<< "\n";
        else if (temp1y == 1)
            cout << ans[temp2x - 1][temp2y - 1] - ans[temp1x - 2][temp2y - 1]<< "\n";
        else
            cout << ans[temp2x - 1][temp2y - 1] - ans[temp1x - 2][temp2y - 1] - ans[temp2x - 1][temp1y - 2] + ans[temp1x - 2][temp1y - 2] << "\n";
    }
}