BOJ 11660 구간 합 구하기 5

문제

접근 방법

2차원에서의 누적합은 어떤 식을 가져야하는지 case 별로 따지다가 시작점들에 offset을 주면 index error를 생각하지 않고 하나의 식으로 해결할 수 있다는 것을 깨달았다.

2차원에서의 누적합은 다음과 같이 구하면 된다: nums[i][j] += (-nums[i-1][j-1] + nums[i-1][j] + nums[i][j-1])

그 다음은 2차원에서 구간 누적합을 구하는 방법을 그려서 구하면 된다: (nums[x2][y2] - nums[x1-1][y2] - nums[x2][y1-1] + nums[x1-1][y1-1])

2차원에서의 누적합 문제라 신선했다.

정답 코드

import sys
input = sys.stdin.readline

n,m = map(int, input().split())

nums = [[0]*(n+1)]

for _ in range(n):
  nums.append([0] + list(map(int, input().split())))

# 2차원 구간합 구하기
'''
왼쪽, 위, 오른쪽 대각선을 자기한테 더하면 된다.

맨 위에 있는 애들은 왼쪽 애들로 더하면 되고

중간에 있는 애들을 세 숫자들로 더하면 되고

맨 밑에 있는 애들을 왼쪽과 위 숫자들로 더하면 된다.

맨 왼 쪽에 있는 애들은 위쪽으로만 더해지면 된다.

하지만 맨 앞자리들에 0을 채워놓으면 이런 짓을 안해도 된다.

'''

for i in range(1,n+1):
  for j in range(1,n+1):
    nums[i][j] += (-nums[i-1][j-1] + nums[i-1][j] + nums[i][j-1])

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