[BaekJoon] 2167번: 2차원 배열의 합 (Python)

• Reference
• dp 너무 어렵다..

Solution

import sys
from typing import List


def solution(N: int, M: int, nums1: List[List[int]], nums2: List[List[int]]) -> List[int]:
    answer = []
    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] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + nums1[i - 1][j - 1]

    for num in nums2:
        i, j, x, y = num
        answer.append(dp[x][y] - dp[i - 1][y] - dp[x][j - 1] + dp[i - 1][j - 1])

    return answer


def main() -> None:
    N, M = map(int, sys.stdin.readline().rstrip().split())
    nums1 = []
    for _ in range(N):
        nums1.append(list(map(int, sys.stdin.readline().rstrip().split())))

    K = int(sys.stdin.readline().rstrip())
    nums2 = []
    for _ in range(K):
        nums2.append(list(map(int, sys.stdin.readline().rstrip().split())))

    print(*solution(N, M, nums1, nums2), sep='\n')


if __name__ == '__main__':
    main()