백준 BAEKJOON 11660번 구간 합 구하기 5 [PYTHON/파이썬]

 

 

 

 

 

백준 BAEKJOON 11660번 구간 합 구하기 5 [PYTHON/파이썬]

---

<문제 출처> (SILVER Ⅰ)

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

11660번: 구간 합 구하기 5

 

 

 

 

 

 

<풀이>

2차원 배열의 누적합을 구하여 풀면 된다.

 

https://youtu.be/irLF8gaAoGk?si=8Qjt5fkvGTS-MYYq

해당 링크의 강의 영상을 참고하여 문제를 풀 수 있었다.

 

원본 배열을 A, 누적합 배열을 D로 만들었다.

(문제 속 해당 인덱스를 쉽게 찾기 위해 0번째 인덱스에 0을 추가했다.)

 

 

[원본 배열 A 테이블]

0	0	0	0	0
0	1	2	3	4
0	2	3	4	5
0	3	4	5	6
0	4	5	6	7

 

 

[누적합 배열 D의 초기 테이블]

0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
0	0	0	0	0

 

 

[누적합 배열 D를 채운 테이블]

0	0	0	0	0
0	1	3	6	10
0	3	8	15	24
0	6	15	27	42
0	10	24	42	64

 

 

원본 배열의 데이터를 통해

2차원 배열의 누적합을 구하는 공식은 아래와 같다.

D[i][j] = D[i][j - 1] + D[i - 1][j] - D[i - 1][j - 1] + A[i][j]

 

 

그리고 x1, y1, x2, y2의 좌표를 받아서

해당 구간의 합을 구하는 공식은 아래와 같다.

result = D[x2][y2] - D[x1 - 1][y2] - D[x2][y1 - 1] + D[x1 - 1][y1 - 1]

 

 

 

 

 

<코드>

import sys

input = sys.stdin.readline
N, M = map(int, input().split())

A = [[0] * (N + 1)]
D = [[0] * (N + 1) for _ in range(N + 1)]

# 누적합 배열 초기 설정
for i in range(N):
    A_row = [0] + [int(x) for x in input().split()]
    A.append(A_row)

# 누적합 배열 채우기
for i in range(1, N + 1):
    for j in range(1, N + 1):
        D[i][j] = D[i][j - 1] + D[i - 1][j] - D[i - 1][j - 1] + A[i][j]

# (x1, y1), (x2, y2)의 구간 합 구하기
for _ in range(M):
    x1, y1, x2, y2 = map(int, input().split())
    result = D[x2][y2] - D[x1 - 1][y2] - D[x2][y1 - 1] + D[x1 - 1][y1 - 1]
    print(result)