[Python] 백준 15724 - 주지수 문제 풀이

Overview

BOJ 15724번 주지수 문제 Python 풀이
분류: 다이나믹 프로그래밍 (Dynamic Programming), 누적합 (Prefix Sum)

---

문제 페이지

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

---

풀이 코드

from sys import stdin

input = lambda: stdin.readline().rstrip()

if __name__ == "__main__":
    N, M = map(int, input().split())
    arr = [[0] * (M + 1)] + \
          list([0] + list(map(int, input().split())) for _ in range(N))

    # 누적합 계산
    for i in range(1, N + 1):
        for j in range(1, M + 1):
            arr[i][j] += arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1]

    K = int(input())
    for _ in range(K):
        ay, ax, by, bx = map(int, input().split())
        print(arr[by][bx] - arr[ay - 1][bx] - arr[by][ax - 1] + arr[ay - 1][ax - 1])

다이나믹 프로그래밍과 누적합으로 풀 수 있다. arr 리스트 각 원소에 (0, 0)부터 해당 좌표까지의 합을 계산하여 저장한다. 그리고 구하려는 영역의 합을 구한다.