[백준 11660번] 구간 합 구하기5 (Python/파이썬)

https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

이 문제는 백준 11659번의 상위 문제로 구간합의 성질을 2차원 배열에서 이용한 문제다.

문제를 처음 봤을때 잘 이해가 안갔었는데 밑의 표에서 (2,2)부터 (3,3)까지의 합을 구하라고 한다면 (2,2), (2,3), (2,4), (3,1), (3,2). (3,3) 으로 모두 더하는 문제로 잘못 이해했다.

(이래서 예시를 잘 봐야하는....)

하이튼 (2,2)부터 (3,3)까지의 합이라면 (2,2), (2,3), (3,2), (3,3) 을 더한다.

 

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

11659번 문제와 마찬가지로 전체 구간합에서 일부를 빼는 식으로 생각했다. 

그러기 위해선 합 배열을 먼저 만들어야하는데 문제는 커녕 그거 조차도 생각해내기가 쉽지 않았다.

생각해낸 방법은 n × n 배열을 만들어서 1열과 1행을 먼저 모두 채우고 나머지를 채워나갔다.

<1행 1열>

1	3	6	10
3
6
10

<나머지>

채우고 싶은 좌표가 (i, j) 라면 "(i-1, j) + (i, j-1) - (i-1, j-1) + 원래보드의 (i, j)"로 채웠다. 식은 간단해 보이지만 생각하는 과정까지 손으로 많이 써봤다.

(풀고 나니까 간단해보이는건 국룰...왜 바로 생각을 못했을까)

 

1	3	6	10
3	8	15	24
6	15	27	42
10	24	42	64

 

합 배열을 완성하고 답은 1부터 (x2, y2)까지의 합에서 필요없는 부분을 빼서 구하였다.

시작 부분의 인덱스가 (0,0), (0, 1이상), (1이상, 0), (1이상,1이상)인 경우를 분리하였다.

완성된 코드는 다음과 같다.

(x1,y1)과 (x2,y2)를 입력받을 때는 인덱스가 아닌 좌표로 입력받기 때문에 기본적으로 받은값에서 -1을 해야한다.

합 배열을 만들고 부분합을 구하는 과정은 손으로 직접 표를 그려서 해보는 것이 좋다.

import sys
input = sys.stdin.readline  ## 빠르게 입력 받기
n,m = map(int,input().split())
board = [list(map(int,input().split())) for _ in range(n)]  ## 표를 2차원 배열로 입력받기
sum_board = [[0]*n for _ in range(n)]  ## 구간 합 배열

## 합 배열의 1행과 1열에 처리
sum_board[0][0] = board[0][0]
for i in range(1,n):
  sum_board[i][0] = sum_board[i-1][0] + board[i][0]
  sum_board[0][i] = sum_board[0][i-1] + board[0][i]

## 합 배열 완성
for i in range(1,n):
  for j in range(1,n):
    sum_board[i][j] = sum_board[i-1][j] + sum_board[i][j-1] - sum_board[i-1][j-1] + board[i][j]

## 부분합 구하기
for i in range(m):
  x1, y1, x2, y2 = map(int, input().split())
  x1 -= 1
  y1 -= 1
  x2 -= 1
  y2 -= 1

  if x1 == 0 and y1 == 0:
    print(sum_board[x2][y2])

  elif x1 == 0 and y1 > 0:
    print(sum_board[x2][y2] - sum_board[x2][y1-1])  ## 전체에서 일부를 뻄

  elif x1 > 0 and y1 == 0:
    print(sum_board[x2][y2] - sum_board[x1-1][y2])  ## 전체에서 일부를 뺌

  else:
    print(sum_board[x2][y2] - sum_board[x2][y1-1] - sum_board[x1-1][y2] + sum_board[x1-1][y1-1])  ##전체에서 일부를 뺴고 겹치는걸 더함

 

백준을 풀면서 파이썬에서 리스트만 사용했었지 배열을 사용한 것은 이번이 처음이었다.

(파이썬에서는 배열과 리스트를 구분하지 않지만 풀때는 [0]으로 채워서 배열을 만듦)