구간 합 구하기 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이다.

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

코드1

import sys
input=sys.stdin.readline

N,M=map(int,input().split())
nums=[]
for _ in range(N):
  nums.append(list(map(int,input().split())))
for _ in range(M):
  total=0
  x1,y1,x2,y2=map(int,input().split())
  for i in range(y1-1,y2):
    for j in range(x1-1,x2):
      total+=nums[i][j]
  print(total)

풀이1

우선 직관적으로 생각할 수 있는 가장 간단한 방식으로 코드를 작성하였다. 물론 M의 개수만큼 입력이 주어질 때마다 합을 구하기 때문에 반복되는 계산이 많아 비효율적이고 시간초과가 나왔다.

코드2

import sys
input=sys.stdin.readline

N,M=map(int,input().split())
nums=[]
for _ in range(N):
nums.append(list(map(int,input().split())))
for i in range(N):
for j in range(N):
  if i==0 and j==0:
    nums[i][j]+=0
  elif i==0: 
    nums[i][j]+=nums[i][j-1]
  elif j==0:
    nums[i][j]+=nums[i-1][j]
  else:
    nums[i][j]+=nums[i-1][j]+nums[i][j-1]-nums[i-1][j-1]


for _ in range(M):
y1,x1,y2,x2=map(int,input().split())
ans=nums[y2-1][x2-1]
if x1-1>0:
  ans-=nums[y2-1][x1-2]
if y1-1>0:
  ans-=nums[y1-2][x2-1]
if x1-1>0 and y1-1>0:
  ans+=nums[y1-2][x1-2]
print(ans)

풀이2

불필요한 반복되는 연산을 줄이기 위해서 nums에 입력받은 값 대신 문제 좌표를 기준으로 (1,1)부터의 합을 nums에 저장했다. 이 값을 이용해 포함되지 않는 부분을 빼고 중복된 부분을 더해주는 과정을 통해 (x1, y1)부터 (x2, y2)까지 합을 구할 수 있다. 개인적으로는 문제의 좌표와 코드를 좌표를 헷갈리게 작성해서 좌표를 계산하는데 어려움을 겪었다. 문제의 좌표와 동일하게 첫 줄에 0으로 패딩하는 방식으로 좌표를 통일하는 것도 좋은 방법일 것 같다.