백준 11660 - 구간 합 구하기 5 (Python3)

코드

import sys
input = sys.stdin.readline

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

# n x n 크기의 표
arr = [list(map(int, input().split())) for _ in range(n)]

# DP 테이블 초기화 (2차원)
# 중요!!!
# d = [[0] * (n+1)] * (n+1)
# 위와 같이 *로 테이블을 초기화할 시
# 메모리 참조값이 모두 동일해져
# 값이 모두 통일된다!!!
# 절대 저런식으로 하면 XXXXX
d = [[0 for i in range(n + 1)] for i in range(n + 1)]

# 점화식
for i in range(n):
    for j in range(n):
        d[i+1][j+1] = (d[i][j+1] + d[i+1][j] - d[i][j]) + arr[i][j]


for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    
    # 출력결과 점화식
    result = d[x2][y2] - (d[x1-1][y2] + d[x2][y1-1] - d[x1-1][y1-1])

    print(result)    

문제 해설

누적 합을 DP로 해결하는 문제.

N x N의 표 즉 2차원 배열이 문제로 주어지므로 DP 테이블 또한 2차원 배열로 (처음 값 0) 초기화를 하였다. 이 때, 주석에 적어놓은 것처럼 for문을 이용하지 않고 그냥 곱하기 연산을 사용하여 DP 테이블을 생성하면 점화식을 사용하여 DP 테이블에 값을 넣어줄 때, 각 열 별 메모리 주소값이 모두 동일해져 행 별로 모두 같은 값이 들어가게 되므로 주의해야 한다!!!!

점화식을 도출하는 것에 제법 고생했는데, 과정은 아래와 같다.

01. DP 테이블 점화식

• 위의 그림에서, 분홍색에 들어올 값을 d[i+1][j+1]이라고 하면 해당 위치 이전까지의 DP 테이블의 값들을 모두 구한 후, 현재 arr[i][j]의 값을 따로 더해주면 된다. 이때, 이전까지의 DP 테이블 값에는 노란색 영역이 중복으로 2번 더해지므로 해당 영역의 값은 한 번 따로 빼주어야 한다.

• 이 때, DP 테이블을 편의상 인덱스를 n과 일치시키기 위해 총 길이를 (n+1) * (n+1)로 설정하여 arr[i][j]의 값을 더해주는 코드가 살짝 헷갈릴 수도 있다.

  • 만약 이를 방지하고 싶다면 arr 또한 행과 열에 0을 전부 추가해주면 해결 가능하다.

• # 점화식
  for i in range(n):
      for j in range(n):
          d[i+1][j+1] = (d[i][j+1] + d[i+1][j] - d[i][j]) + arr[i][j]
  

02. 최종 결과 점화식

• 답을 출력하는 과정도 01과 비슷하다.

• 마찬가지로 x2, y2를 구하는 과정에서 이전 영역들의 합을 더해주고, 중복되는 영역은 따로 빼주면 간단하게 답을 도출할 수 있다.

• # 출력결과 점화식
  result = d[x2][y2] - (d[x1-1][y2] + d[x2][y1-1] - d[x1-1][y1-1])