알고리즘 유형 : 누적합, DP
풀이 참고 없이 스스로 풀었나요? : X
https://www.acmicpc.net/problem/11660
소스 코드(파이썬)
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
table = [[0]*(N+1)]
pre_sum = [[0]*(N+1) for _ in range(N+1)]
for _ in range(N):
table.append([0] + [*map(int, input().split())])
# 왼쪽 위 모서리가 (1,1)인 모든 직사각형 합 구해놓기
# DP를 활용한다. 왼쪽 위 모서리가 (1,1), 오른쪽 밑 모서리가 (x,y)인 직사각형의 합은
# pre_sum(x,y) = table(x,y) + pre_sum(x-1,y) + pre_sum(x,y-1) - pre_sum(x-1,y-1)
for row in range(1, N+1):
for col in range(1, N+1):
pre_sum[row][col] = table[row][col] + \
(pre_sum[row-1][col] + pre_sum[row][col-1] - pre_sum[row-1][col-1])
for _ in range(M):
x1, y1, x2, y2 = map(int, input().split())
result = pre_sum[x2][y2] - (pre_sum[x1-1][y2] + pre_sum[x2][y1-1] - pre_sum[x1-1][y1-1])
print(result)풀이 요약
-
질의가 주어졌을 때, 이를 그때그때 일일이 직사각형 합을 구해서 출력하면, 최대 1000x100000 = 10^8의 연산이 발생해 TLE다.
이 문제는 DP로 접근한다.
우선 왼쪽 위 모서리가 (x1, y1) 오른쪽 아래 모서리가 (x2, y2)인 임의의 직사각형의 합을 구하는 방법을 생각해보자.
여러 가지 방법이 있겠지만,
위 그림에서,
보라색 상자의 합 = 분홍색 상자 - (초록 + 노랑 - 파랑)이다.처참한 똥퀄 그림.. 죄송합니다..여기서 눈치챘겠지만 문제의 답을 구하기 위해선 왼쪽 위 모서리가 (1,1)인 직사각형들의 합 값이 필요하다는 것을 알 수 있다.
왼쪽 위 모서리가 (1,1)인 직사각형은 N=1024인 경우에는 자연수 거듭제곱 시그마 공식에 따라, 쌩으로 모두 구하려면 10^9의 시간복잡도가 필요하다. 그래서 여기에 DP를 활용한다.
-
전체 문제를 부분 문제로 정의해보자.
(1,1)부터 (x,y)의 직사각형의 합을 pre_sum(x,y)라고 하면,
pre_sum(x,y) = (x,y)자체값 + pre_sum(x-1,y) + pre_sum(x,y-1) - pre_sum(x-1,y-1)
그림으로 표현하면,
보라색 상자 = 파랑 + 주황 + 초록 - 분홍이다.이 것을 바텀업 방식으로, (1,1)부터 (1,1)까지의 직사각형부터 시작해서 크기를 키워나가면서 모든 직사각형을 구해준다.
이렇게 구해진 자료는 곧 2차원에서의 누적 합이라고도 볼 수 있다.이렇게 구한 직사각형 합들로 질의로 들어온 직사각형의 합을 구해주면 된다.
배운 점, 어려웠던 점
-
이번 문제에서도 누적합 구하는 것을 1차원적으로만 생각해서 계속 TLE가 떴다.
다른 사람 풀이에서 2차원에서의 누적합을 DP로 구하는 아이디어를 참고해서 풀었는데, 1차원 누적합의 개념에 사고가 갇혀 넓게 보질 못한 것 같다. 더 넓은 시각을 가지고 문제에 접근하려 노력해야겠다.
