[백준] 11660 구간 합 구하기 5 python

문제

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

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

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

출력

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

예제 입력 1 복사

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

예제 출력 1 복사

27
6
64

 

 

포기했던 DP를 살려본 하루.. 포기했던 이유가 있어 ㅋㅎㅎㅋㅎ

 

돌아서면 또 까먹을 것 같어

 

initialize

n + 1 범위로 버퍼를 준다. 따라서 dp[i][j] 에 graph[i][j]가 아니라 graph[i-1][j-1].

양 x,y [0] [0] 막대기들이 0으로 되어있게끔.

=> [[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]] dp

dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]


for i in range(1, n+1):
    for j in range(1, n+1):
        dp[i][j] = dp[i-1][j] + dp[i][j-1] + graph[i - 1][j - 1] - dp[i-1][j-1]

DP내에서 시작점 끝점 변형한 부분합 (아래는 DP 이차원배열)

전체 부분합에서 대각선의 부분합을 뺀다 이 때 겹치는 대각선의 부분합이 2번 빼지니까 한번 더해준다.

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))

test = []
for _ in range(m):
    test.append(list(map(int, input().split())))

dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]


for i in range(1, n+1):
    for j in range(1, n+1):
        dp[i][j] = dp[i-1][j] + dp[i][j-1] + graph[i - 1][j - 1] - dp[i-1][j-1]

for x1, y1, x2, y2 in test:
    ans = 0

    ans = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]

    print(ans)


# def findSum(x1, y1, x2, y2):
#     global graph
#     xLen = x2 - x1 + 1
#     yLen = y2 - y1 + 1
#     dp = [[0 for _ in range(yLen)] for _ in range(xLen)]
#     dp[0][0] = graph[x1][y1]
#     # print(dp)

#     # i
#     for i in range(1, xLen):
#         dp[i][0] = dp[i - 1][0] + graph[x1 + i][y1]

#     # j
#     for j in range(1, yLen):
#         dp[0][j] = dp[0][j - 1] + graph[x1][y1 + j]

#     # print(dp, "dd")
#     for i in range(xLen - 1):
#         for j in range(yLen - 1):
#             dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j] + graph[x1 + i + 1][y1 + j + 1] - dp[i][j]
    
#     # print(dp)
#     return dp[xLen - 1][yLen - 1]
    

    

# dp 같다.
# dp[n]은 0부터 n까지 의 합.