[백준] 11660번 - 구간합 구하기 5

1. 문제 (링크)

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이다.

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

2. 핵심 아이디어

• 그림을 그려서 아래의 공식들을 도출하자!
• 구간 합 구하는 공식
  • 원래 배열 -> o
  • 구간합 배열 -> s

    s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1]+o[i][j]

• 질의에 대한 응답

  s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]

3. 소스코드 (파이썬)

import sys

input = sys.stdin.readline
n, queryNum = map(int, input().split())
orgin_arr = [[0] * (n + 1)]  #0번째 행은 0으로 패딩

#구간합 배열 초기화
sum_arr = [[0] * (n + 1) for _ in range(n + 1)]

#원본 배열 입력 받기
for i in range(n):
  row = [0] + [int(x) for x in input().split()]  #앞에 0으로 패딩해서 입력받기, 여기 주의!
  orgin_arr.append(row)  #행 붙이기

#구간합 배열 구성
for i in range(1, n + 1):  #행
  for j in range(1, n + 1):  #열
    sum_arr[i][j] = sum_arr[i-1][j] + sum_arr[i][j-1] - sum_arr[i-1][j-1] + orgin_arr[i][j]

#질의에 응답하기
for i in range(queryNum):
  x1, y1, x2, y2 = map(int, input().split())
  result = sum_arr[x2][y2] - sum_arr[x1-1][y2] - sum_arr[x2][y1-1] + sum_arr[x1-1][y1-1]
  print(result)

4. 코드 포인트

• 이차원 배열 초기화

  sum_arr = [[0] * (n + 1) for _ in range(n + 1)]

• 여러 행 입력 받기

  for i in range(n):
  row = [0] + [int(x) for x in input().split()]  #앞에 0으로 패딩해서 입력받기, 여기 주의!
  orgin_arr.append(row)  #행 붙이기