[🥈1 / 백준 15724 / 파이썬] 주지수

 

15724번: 주지수

 

문제

네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 주지수를 만들기 위해서 일정한 직사각형 범위 내에 살고 있는 사람 수를 참고 자료로 쓰고 싶어한다.

진경대왕은 굉장히 근엄한 왕이기 때문에 당신에게 4개의 숫자로 직사각형 범위를 알려줄 것이다.

예를 들어, 위와 같이 사람이 살고 있다고 가정할 때 <그림 1>의 직사각형 범위의 사람 수를 알고 싶다면 진경대왕은 네 개의 정수 1 1 3 2를 부를 것이다. 마찬가지로 <그림 2>는 1 1 1 4, <그림 3>은 1 1 4 4가 될 것이다.

진경대왕을 위하여 이 참고 자료를 만들어내는 프로그램을 작성해보자.

입력

첫째 줄에 영토의 크기 N, M(1 ≤ N, M ≤ 1,024)이 주어진다.

다음 N개의 줄에는 M개의 정수로 단위 구역 내에 살고 있는 사람 수가 주어진다. 각 단위 구역 내에 살고 있는 사람 수는 100명 이하이며, 각 단위 구역 별 최소 1명의 사람은 살고 있다.

그 다음 줄에는 진경대왕이 인구 수를 궁금해하는 직사각형 범위의 개수 K(1 ≤ K ≤ 100,000)가 주어진다.

다음 K개의 줄에는 네 개의 정수로 직사각형 범위 x1, y1, x2, y2가 주어진다(x1 ≤ x2, y1 ≤ y2).

출력

K개의 줄에 순서대로 주어진 직사각형 범위 내에 살고 있는 사람 수의 합을 출력한다.

 

예제 입력  4 4 9 14 29 7 1 31 6 13 21 26 40 16 8 38 11 23 3 1 1 3 2 1 1 1 4 1 1 4 4

예제 출력  102 59 293

 

풀이

 

해당하는 범위의 합을 출력하는 문제이다.

만약 원소를 하나하나 구해서 더하여 출력한다면 O(n*m*k) 의 시간복잡도를 요구할 것이다.

따라서 누적 합을 통해 빠르게 범위의 합을 구해야 한다.

 

알고리즘의 기본 원리는 1차원 배열의 누적합과 크게 다르지 않다.

dp를 이용하여 누적 합 배열을 구하고, 이를 적절히 가감하여 원하는 범위의 합을 구한다.

 

일단 인덱스 0,0 부터 끝까지의 누적합을 차례대로 더해나가며 구한다.

점화식은 다음과 같다.

 

dp[i][j] = area[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]

 

예제로 누적 합을 구해보자면 다음과 같다.

 

 

연산을 보다 쉽게 하기 위해 빈 공간을 추가로 할당했다.

 

이제 밑의 그림에서 파란색 영역을 구해보고자 한다.

그렇다면 인덱스 0,0 부터 파란색 영역 오른쪽 아래까지의 합에 해당하는 234를 더해주고,

빗금 친 부분인 39, 52를 빼준 뒤, 빗금에서 겹친 부분인 초록색 영역에 해당하는 9를 한 번 더해주면 된다.

 

식은 다음과 같다.

 

dp[i][j] - dp[x-1][j] - dp[i][y-1] + dp[x-1][y-1]

 

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
area = [list(map(int,input().split())) for _ in range(n)]

dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1,m+1):
        dp[i][j] = area[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]

for _ in range(int(input())):
    x,y,i,j = map(int,input().split())
    print(dp[i][j] - dp[x-1][j] - dp[i][y-1] + dp[x-1][y-1])