백준 11660번 구간의 합 구하기 5

이번 문제는 부분합을 이용하는것이지만 한개의 리스트로 이루어진 것이 아니라 이중리스트 2차원 배열을 이용한는것이다 따라서 부분합을 구할때 처음부터 차례대로 부분합을 구하는 방법을 사용하면 이문제를 해결하기 어렵다

 

 

 

문제 이해

(x1,y1)과 (x2,y2)가 주어지면 그사이에 만들어지는 정사각형의 부분합을 구하는 것이다

이 사이에 속하는 부분합을 구하기 위해서 부분합을 어떻게 만들것인가를 생각해야 한다

위 사진처럼 입력을 받았을 때 7번까지의 부분합은 1+2+6+7로 만들어 그위치에 저장하고 14번까지의 부분합은 1+2+3+4+6+7+8+9+11+12+13+14가 되도록 부분합을 만든다

이런 부분합을 만들어 2중 리스트로 저장한다

위 사진에서 우리가 원하는 구간 파란색의 부분합을 구하기위해서는 D까지의 부분합 D -C-D+A(두번 뺐으므로 한번 더 해준다) 가 된다

문제 풀이

import sys

N,M= map(int,sys.stdin.readline().split())
list1 = [] # 2차원 배열로 저장할 리스트 
list_sum = [[0]*N for i in range(N)]
list2 = []
for i in range(0,N):
    a = list(map(int,sys.stdin.readline().split()))
    list1.append(a)

for i in range(0,N): #누적합
    a = 0

    for j in range(0,N):

        if i == 0:
            a += list1[i][j]
            list_sum[i][j] = a

        elif j == 0:
            a = list_sum[i-1][0] + list1[i][0]
            list_sum[i][j] = a

        else:
            list_sum[i][j] = list_sum[i-1][j] + list_sum[i][j-1] + list1[i][j] - list_sum[i-1][j-1]


for k in range(0,M): #부분합 구하기
    key = 0
    x1,y1,x2,y2 = map(int,sys.stdin.readline().split())
    x1 = x1-1
    y1 = y1 -1
    x2 = x2 -1
    y2 = y2 -1

    if x1==x2 and y1==y2:
        key = list1[x1][y1]

    elif x1 == 0 and y1 == 0:
        key = list_sum[x2][y2]

    elif x1 == 0:
        key = list_sum[x2][y2] - list_sum[x2][y1-1]

    elif y1 == 0:
        key = list_sum[x2][y2] - list_sum[x1-1][y2]

    else:
        key = list_sum[x2][y2] - list_sum[x2][y1-1] - list_sum[x1-1][y2] + list_sum[x1-1][y1-1]
    print(key)

풀이를 더 간단하게 할 수 있는데 난잡하게 적어놨,,,