[백준][Python] 15724 주지수 - Python

문제 링크

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

 

# problem

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

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

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

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

---

# input

첫째 줄에 영토의 크기 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).

---

# output

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

---

# 풀이

처음 문제를 보고 모든 직사각형의 칸을 하나씩 들리며 합연산을 하는 방법을 생각했다.

# 시간 초과 코드
def get_people(x1, y1, x2, y2) :
    people = 0
    for i in range(x1 - 1, x2) :
        for j in range(y1 - 1, y2) :
            people += arr_2d[i][j]
    return people
    

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

for i in range(k) :
    x1, y1, x2, y2 = scope[i]
    people = get_people(x1, y1, x2, y2)
    print(people)

하지만 입력 조건을 고려하여 최악의 시간복잡도를 생각하면, n = 1024, m = 1024, k = 10000 이므로 약 백억 = 10초로 시간 초과가 발생한다. 이를 해결하기 위해 누적합을 사용하였다.

# 누적합 코드
n, m = map(int, input().split())
arr_2d = [list(map(int, input().split())) for _ in range(n)]
k = int(input())
scope = [list(map(int, input().split())) for _ in range(k)]

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] = arr_2d[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]

for i in range(k):
    x1, y1, x2, y2 = scope[i]
    print(dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1])

어느 한 칸의 누적합 = 대각선칸 입력값 + 오른칸 누적값 + 윗칸 누적값 - 대각선칸 누적값 이므로, index out 에러가 발생하지 않도록 누적합을 저장할 2차원 배열(dp)을 (n+1) * (m+1)으로 설정하였다.