백준 11660번 : 구간 합 구하기 5 in Python

11660번: 구간 합 구하기 5

 

www.acmicpc.net

이 문제는 N*N개의 수가 N*N 크기의 표에 채워져 있을 때 (x1, y1)부터 (x2, y2)까지 합을 구하는 문제이다. 즉, 이전의 구간 합 구하기 4 문제와 유사하나 배열이 아닌 행렬에서의 구간 합을 구해야 한다.

백준 11659번 : 구간 합 구하기 4 in Python

11659번: 구간 합 구하기 4 www.acmicpc.net 이 문제는 수 N개가 주어졌을 때 i번째 수부터 j번째 수까지 합을 구하는 문제이다. 만약 주어지는 (i, j) 쌍의 수가 적다면 단순히 i번째 수부터 j번째 수까지 더하면..

wanna-be-developer-yjh.tistory.com

행렬에서는 어떻게 구간 합을 간단히 구할 수 있을까? 만약 (1, 1)에서 (i, j)까지의 합을 구하고자 한다면, (1, 1)부터 (i-1, j)까지의 합과 (1, 1)부터 (i, j-1)까지의 합을 이용해야 할 것이다. 다만 두 개를 합하기만 하면 (1, 1)부터 (i-1, j-1)까지의 합을 중복해서 더하는 것이기 때문에 이를 한 번 빼 준다.

이런 방식으로 임의의 i, j에 대해 (1, 1)부터 (i, j)까지의 구간 합을 구할 수 있다. 그렇다면 (x1, y1)부터 (x2, y2)까지의 합은 어떻게 구할 수 있을까? 일단 (1, 1)부터 (x2, y2)까지의 합에서 (1, 1)부터 (x1-1, y2)까지의 합과 (1, 1)부터 (x2, y1-1)까지의 합을 빼야 할 것이다. 그런데 두 합을 뺄 경우 (1, 1)부터 (x1-1, y1-1)까지 합을 두 번 빼게 되므로 이를 한 번 더해줘야 할 것이다.

이를 코드로 구현하면 다음과 같다.

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
nums = [[0]*(N+1)]
for _ in range(N):
    nums.append([0] + list(map(int, input().split())))
# (1, 1)부터 (i, j)까지의 합을 구해 nums[i][j]에 저장한다.
for i in range(1, N+1):
    for j in range(1, N+1):
        nums[i][j] += nums[i][j-1] + nums[i-1][j] - nums[i-1][j-1]
for _ in range(M):
    x1, y1, x2, y2 = map(int, input().split())
    # (1, 1)부터 (i, j)까지의 합을 구한 것을 바탕으로 (x1, y1)부터 (x2, y2)까지 합을 구한다.
    res = nums[x2][y2] - nums[x1-1][y2] - nums[x2][y1-1] + nums[x1-1][y1-1]
    print(res)