백준 #11660 - 구간 합 구하기 5

 

문제

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

출력

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

예제 입력 1

4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4

예제 출력 1

27
6
64

예제 입력 2

2 4
1 2
3 4
1 1 1 1
1 2 1 2
2 1 2 1
2 2 2 2

예제 출력 2

1
2
3
4

 

 

 

---

 

 

우선 문제를 보자마자 생각난 방법이 있었지만 아무래도... 시간초과가 날 것 같았다.

그래서 누적합과 부분합을 구하여 풀어야겠다는 생각이 들긴 했는데... 2차원 배열의 누적합은 어떻게 구할 것인가.

 

일단 행별 누적합을 구한 후, 열 별 누적합을 구하니 2차원 배열의 누적합을 구할 수 있었다.

 

그리고는 부분합을 구해야 하는데, 2차원 배열의 부분합은 마치 집합의 공식처럼 일정 부분을 더하고 빼며 구해줘야 한다.

이것도 생각해보면 어렵지 않은데 자꾸 인덱스 오류가 떠서 곤란했다.

 

알고보니 0행 0열에 패딩을 넣어주고 시작해야 했던 것...

0행에 패딩을 넣어주는건 생각이 났는데 이상하게 0열에 패딩을 넣는건 익숙지 않게 느껴져버렸다.

 

 

import sys
input = sys.stdin.readline

n , m = map(int, input().split()) # 표의 크기, 구해야 하는 횟수
graph = [[0] * (n + 1)]
for _ in range(n):
    row = [0] + list(map(int, input().split()))
    graph.append(row)

# 행의 누적합
for i in range(0, n + 1):
    for j in range(0, n):
        graph[i][j + 1] += graph[i][j]

'''
[[0, 0, 0, 0],
 [1, 3, 6, 10], 
 [2, 5, 9, 14], 
 [3, 7, 12, 18], 
 [4, 9, 15, 22]]
'''

# 열의 누적합
for i in range(0, n):
    for j in range(0, n + 1):
        graph[i + 1][j] += graph[i][j]

'''
[[0, 0, 0, 0],
 [1, 3, 6, 10], 
 [3, 8, 15, 24], 
 [6, 15, 27, 42], 
 [10, 24, 42, 64]]
'''

for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    ans = graph[x2][y2] - graph[x1 - 1][y2] - graph[x2][y1 - 1] + graph[x1 - 1][y1 - 1]
    print(ans)