[BOJ] 2167번: 2차원 배열의 합

https://www.acmicpc.net/problem/2167


주어진 매 쿼리에 대해 배열의 합을 이중 for문을 돌면서 직접 원소 하나하나를 더해 계산하면 최악의 경우 시간복잡도는 O(KNM)이어서 제한시간을 넘길 가능성이 큽니다. 그렇기 때문에


D[i][j] : (1,1)부터 (i, j)까지를 더한 합을 미리 O(NM)에 채우고


i, j, x, y로 들어오는 쿼리에 대해 D[x][y] - D[x][j - 1] - D[i - 1][y] + D[i - 1][j - 1]를 계산하면 O(K)로 해결할 수 있습니다. 인덱싱을 0부터 할 수도 있고 1부터 할 수도 있는데 1로 하면 예외처리를 별로 안해줘도 돼서 편합니다.


https://github.com/encrypted-def/BOJ/blob/master/2193.cpp

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 3046번: R2  (0) 2017.12.31
[BOJ] 9095번: Adding 1s, 2s, and 3s  (0) 2017.12.31
[BOJ] 2443번: 별찍기 - 6  (1) 2017.12.31
[BOJ] 2442번: 별찍기 - 5  (0) 2017.12.31
[BOJ] 1085번: 직사각형에서 탈출  (0) 2017.12.31
[BOJ] 1009번: 분산처리  (0) 2017.12.31
  Comments