파이썬 알고리즘 305번 | [백준 11659, 11660번] 누적합 유형들 (1차원, 2차원)

305. 누적합 유형들 (1차원, 2차원)

1) 어떤 전략(알고리즘)으로 해결?

2) 코딩 설명

<내 풀이>

(1) 1차원 누적합

import sys

N,M = map(int,sys.stdin.readline().rstrip().split())
lis = list(map(int,sys.stdin.readline().rstrip().split()))
accum = [0 for _ in range(N+1)] # 맨 앞은 0 - 누적합 시작은 인덱스 1부터

for i in range(len(lis)) : 
    accum[i+1] = accum[i]+lis[i]

for _ in range(M) : 
    i,j = map(int,sys.stdin.readline().rstrip().split())
    print(accum[j]-accum[i-1])
    

(2) 2차원 누적합

import sys

def make_sum(graph) : 
    sum_list = [ [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) : 
            # 2차원 배열도 행과 열에 0 가득 배열로 왼쪽 윗쪽에 테두리쳐줘야 합니다.
            sum_list[i][j] = graph[i][j]+sum_list[i-1][j]+sum_list[i][j-1]-sum_list[i-1][j-1]
    return sum_list

def accum_sum(x1,y1,x2,y2) : 
    return sum_list[x2][y2]-sum_list[x1-1][y2]-sum_list[x2][y1-1]+sum_list[x1-1][y1-1]

N,M = map(int,sys.stdin.readline().rstrip().split())
graph = [[0 for _ in range(N+1)]]

for i in range(N) :
    graph.append([0]+list(map(int,sys.stdin.readline().rstrip().split())))

sum_list = make_sum(graph) # 누적합 배열 만들기 

for _ in range(M) : 
    x1,y1,x2,y2 = map(int,sys.stdin.readline().rstrip().split())
    print(accum_sum(x1,y1,x2,y2))

<배운 점>