[파이썬] 2차원 누적합 알고리즘(백준 11660 합 구하기 5)

백준 11660 구간 합 구하기 5

 

시간초과 발생 코드

import sys

n, m = map(int, sys.stdin.readline().split())

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

for i in range(m):
    hap = list(map(int, sys.stdin.readline().split()))
    
    total = 0
    for p in range(hap[0] - 1, hap[2]):
        for q in range(hap[1] - 1, hap[3]):
            total += nums_list[p][q]
    
    print(total)

 

 

합을 구하는 횟수 m이 10만까지이고, 시간 제한이 1초라서, 이중 for문으로 작성하면서 시간초과가 발생할 거라 예상했지만 실제로 시간 초과가 발생했다.

 

시간초과를 면하기 위해서는 DP를 활용하여 누적합을 저장한 후 부분합을 구하는 방식으로 해야 한다.

 

반응형

 

 

import sys

n, m = map(int, sys.stdin.readline().split())

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

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

for i in range(1, n + 1):
    for k in range(1, n + 1):
        sum_arr[i][k] = nums_list[i-1][k-1] + sum_arr[i-1][k] + sum_arr[i][k-1] - sum_arr[i - 1][k - 1]
    
for _ in range(m):
    hap = list(map(int, sys.stdin.readline().split()))
    x1, y1, x2, y2 = hap[0] - 1, hap[1] - 1, hap[2] - 1, hap[3] - 1

    total = sum_arr[x2+1][y2+1] - sum_arr[x1][y2+1] - sum_arr[x2+1][y1] + sum_arr[x1][y1]
    print(total)

 

 

DP(다이나믹 프로그래밍)을 이용해서 코드를 짜면 시간 초과가 발생하지 않는다.

DP를 수행할 sum_arr를 선언하는데, 0으로 모두 초기화를 한다.

 

SMALL

** DP를 n+1 * n+1 크기로 초기화하는 이유

문제에서 n*n 배열을 사용하도록 했는데, DP 배열에 누적합을 저장하는 알고리즘이 [i-1][k-1]처럼 이전 요소를 사용한다.

여기서 인덱스 오류를 방지하기 위해 DP 배열을 선언할 때는 n+1 * n+1로 하여 0이 계산에 사용될 수 있게 한다.

 

** sum_arr[i][k]를 저장하는 연산의 의미

sum_arr[i][k] = nums_list[i-1][k-1] + sum_arr[i-1][k] + sum_arr[i][k-1] - sum_arr[i - 1][k - 1]

 

아래는 sum_arr[4][4]가 27이 어떻게 됐는지 예시로 든 이미지이다.

 

(오타 수정 : sum_arr[3][4]는 27이 아닌 45이다.)

 

728x90

 

 

이후 hap 리스트에 x1, y1, x2, y2를 저장하여 수행한 연산은 부분합을 구하는 계산을 수행하여 계산한다.

마찬가지로 중복 부분을 따져 계산해주면 된다.