https://www.acmicpc.net/problem/15724
15724번: 주지수
네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은
www.acmicpc.net
문제
네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 주지수를 만들기 위해서 일정한 직사각형 범위 내에 살고 있는 사람 수를 참고 자료로 쓰고 싶어한다.
![](https://blog.kakaocdn.net/dn/tbnw2/btstfSluYRO/09VUK6BwuKo8F2ePpR8xo0/img.jpg)
진경대왕은 굉장히 근엄한 왕이기 때문에 당신에게 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개의 줄에 순서대로 주어진 직사각형 범위 내에 살고 있는 사람 수의 합을 출력한다.
풀이
Code
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
graph = [[0 for _ in range(m+1)]] + [[0] + list(map(int, input().split())) for _ in range(n)]
# 1. 누적합 배열 생성
prefix_sum = graph.copy()
# 2. 누적합 생성
for i in range(1, n + 1) :
for j in range(1, m + 1) :
prefix_sum[i][j] += prefix_sum[i-1][j] + prefix_sum[i][j-1] - prefix_sum[i-1][j-1]
t = int(input())
for _ in range(t) :
x1, y1, x2, y2 = map(int, input().split())
# 3. 점화식에 따른 사람 수의 합 출력
print(prefix_sum[x2][y2] - prefix_sum[x2][y1-1] - prefix_sum[x1-1][y2] + graph[x1-1][y1-1])
'Coding Test > Baekjoon' 카테고리의 다른 글
[Python/BOJ] 15922. 아우으 우아으이야!! (0) | 2023.09.08 |
---|---|
[Python/BOJ] 11497. 통나무 건너뛰기 (0) | 2023.09.05 |
[Python/BOJ] 1900. 레슬러 (0) | 2023.09.05 |
[Python/BOJ] 8972. 미친 아두이노 (0) | 2023.09.04 |
[Python/BOJ] 1043. 거짓말 (0) | 2023.09.03 |