11660 - 구간 합 구하기 5
📌 문제
N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.
예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.
여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.
표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.
📋 코드
N, M = map(int, input().split())
graph = [[0] + list(map(int, input().split())) for _ in range(N)]
graph = [[0 for _ in range(N+1)]] + graph
pos = [list(map(int, input().split())) for _ in range(M)]
for i in range(1, N+1):
for j in range(1, N+1):
graph[i][j] += graph[i][j-1]
for i in range(1, N+1):
for j in range(1, N+1):
graph[i][j] += graph[i-1][j]
for x1, y1, x2, y2 in pos:
if x1 == 1 and y1 == 1:
print(graph[x2][y2])
elif x1 == 1:
print(graph[x2][y2] - graph[x2][y1-1])
elif y1 == 1:
print(graph[x2][y2] - graph[x1-1][y2])
else:
print(graph[x2][y2] - graph[x2][y1-1] - graph[x1-1][y2] + graph[x1-1][y1-1])💡 한마디
구간 합 구하기 4를 2차원 배열로 확장한 형태이다. 행의 누적과 열의 누적을 구해놓고 예외 처리만 잘 해주면 쉽게 풀 수 있는 문제이다.
