[알고리즘 문제] 백준 11660번 구간 합 구하기 5

11660번: 구간 합 구하기 5 (acmicpc.net)

11660번: 구간 합 구하기 5

 

문제

 2차원 배열에서 지정한 사각형 구역 내의 합을 구하는 문제입니다.

 

아이디어

 구간합 방법의 2차원 예입니다.

 

 1차원 배열에서의 구간 합의 경우, 0부터 i까지의 합을 캐시하면, 구간 합은 O(1) 시간에 구할 수 있습니다. 

 

 

 2차원의 경우도, 같은 아이디어를 적용해 O(1) 시간에 구간합을 구할 수 있습니다.

 단, 2차원이 되면서 영역을 빼고 더하는 부분이 생긴건 유의합니다.

 

c(i, j) = data(i, j) + c(i-1, j) + c(i, j-1) – c(i-1, j-1)

합을 캐시할 때도 2차원 구조에 맞춰 더하고 빼줍니다.

 

 1. 입력받은 데이터에 대해 (0,0)에서 (i, j)까지 합 정보를 저장합니다. O(n)

 2. 해당 정보를 바탕으로 들어오는 쿼리를 계산합니다. O(m)

 

모든 값이 최대일 때 최대 합은 1024 * 1024 * 1000 = 약 10억 이니 int 범위로 충분합니다.

 

코드

// No.11660

#include <iostream>
using namespace std;

int N, M;
int table[1026][1026]; // use 1~1024
int cache[1026][1026];

void set_table() {
    for(int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cache[i][j] = table[i][j] + cache[i-1][j] + cache[i][j-1] - cache[i-1][j-1];
        }
    }
}

uint64_t get_sum(int x1, int y1, int x2, int y2) {
    int sum = cache[y2][x2] - cache[y2][x1-1] - cache[y1-1][x2] + cache[y1-1][x1-1];
    return sum;
}

int main(void) {
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++) {
            scanf("%d", &table[j][i]);
        }

    set_table();

    for (int i = 0; i < M; i++) {
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        cout << get_sum(x1, y1, x2, y2) << '\n';
    }
}

 

기타

 이 문제의 경우 std::cin을 사용하면 시간 초과가 발생합니다.

 알고리즘 문제를 풀 때, 입력 데이터가 많아지면 iostream의 느린 속도로 인해 문제가 생길 수 있는데,

ios_base::sync_with_stdio(false);
cin.tie(NULL);

 

이 둘을 추가하면 입력 속도를 향상할 수 있습니다.

 

 ios_base::sync_with_stdio(false);는 c의 stdio와의 동기화를 해제합니다.

 c++은 기본적으로 c의 입출력 시스템을 동시에 사용하기 위해,

 c와 c++의 스트림을 동기화하는데, 이는 thread safe하지만 성능저하를 일으킵니다.

std::ios_base::sync_with_stdio - cppreference.com

 

 사용자와 입출력을 하는 프로그램의 경우 질문과 대답이 섞여서는 않되기에,

 c++은 I/O작업 전 연결된 출력 스트림을 플러시합니다.

 std::ios::tie(ostream* tiestr);은 io와 연결될 스트림을 지정하는데 NULL을 전달하면 이 과정을 생략합니다.

cplusplus.com/reference/ios/ios/tie/