[백준 BOJ_11660] 구간 합 구하기 5 Python 풀이

출처: 백준 온라인 저지

문제

풀이

동적계획법으로 풀어주었습니다.

graph의 각각 첫 번째 행과 열(graoh[0][i], graph[i][0])은 이 전의 값을 누적하며 더해주었습니다.

첫 번째 행과 열을 제외한 나머지 칸들은 왼쪽에 있는 값(graph[x-1][y])과 위쪽에 있는 값(graph[x][y-1])을 더해주고, 각각의 누적합들은 대각선에 있는 값(graph[x-1][y-1])을 포함하고 있기 때문에 한 번만 더해주기 위해 대각선의 값을 빼주어야합니다.

이렇게 구한 누적합들은 시작점이 (1, 1)일 경우의 누적합이기 때문에 시작점이 (1, 1)이 아닐 경우에는 범위 밖에 있는 값들을 빼주어야 합니다.

exclude에 빼주어야할 값을 누적해서 더해줍니다. 빼주어야 하는 값들은 다음과 같습니다.

• x1이 1보다 클 때, (x1-1, y1)까지의 누적합
• y1이 1보다 클 때, (x1, y1-1)까지의 누적합

이 전에 누적합을 구해줄 때 대각선에 있는 값이 두 번 더해진다고 한 것과 동일하게 (x1-1, y1-1)까지의 누적합이 두 번 빼지게 되기 때문에 해당 누적합을 한 번만 빼지도록 두 번 빼졌다면 한 번 더해주어야 합니다.

마지막에는 끝점(x2, y2)의 누적합에서 exclude를 빼준 값을 출력해주면 됩니다.

코드

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
for i in range(1,N):
  graph[0][i] += graph[0][i-1]
  graph[i][0] += graph[i-1][0]
for x in range(1, N):
  for y in range(1,N):
    graph[x][y] += graph[x-1][y] + graph[x][y-1] - graph[x-1][y-1]
for _ in range(M):
  x1, y1, x2, y2 = map(int, input().split())
  exclude = 0
  if x1 > 1:
    exclude += graph[x1-2][y2-1]
  if y1 > 1:
    exclude +=  graph[x2-1][y1-2]
  if x1 > 1 and y1 > 1:
    exclude -=  graph[x1-2][y1-2]
  print(graph[x2-1][y2-1]-exclude)