[Python/백준] 구간 합 구하기 5

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

---

처음에 dp의 누적합을 두고 풀어야 겠다는 생각을 했습니다.

2024.09.28 - [분류 전체보기] - [Python] 누적합 알고리즘

[Python] 누적합 알고리즘

 

 

---

1. 첫 번째 방법

각 행마다 누적합을 구하고, x1행부터 x2행까지 반복문을 돌면서 값을 더한다.

 

 

누적합 리스트 sum_graph를 구하게 되면

sum_graph [x1][y2] - sum_graph [x1][y1-1]

sum_graph [x2][y2] - sum_graph [x2][y1-1]

을 더해주는 것입니다

 

식을 써본다면

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
sum_graph = [[0]*(n+1)]
for _ in range(n):
    lists = (list(map(int, input().split())))
    sumlists = [0] * (n+1)
    for i in range(1, n+1):
        sumlists[i] = sumlists[i-1] + lists[i-1]
    sum_graph.append(sumlists)
    
# print(sum_graph)

for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    
    summ = 0
    # x1행부터x2행까지
    for x in range(x1, x2+1):
        # y1열~y2열까지
        summ += sum_graph[x][y2] - sum_graph[x][y1-1]
    print(summ)

 

하지만 이렇게 되면 x1부터 x2까지의 행을 돌기 때문에 시간 복잡도가 늘어납니다

시간초과

---

2. 두 번째 방법

현재 인덱스가 x, y일 때 처음부터 x, y까지 인덱스의 합을 저장한다

구하는 법

graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))
sum_graph = [[0]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, n+1):
        sum_graph[i][j] = sum_graph[i-1][j] + sum_graph[i][j-1] - sum_graph[i-1][j-1] + graph[i-1][j-1]

 

 

누적합 2차원 리스트를 만들었다

 

 

 

 

(2,2)부터 (3,3)을 구한다고 한다면

 

 

 

for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    print(sum_graph[x2][y2] -sum_graph[x2][y1-1] -sum_graph[x1-1][y2] + sum_graph[x1-1][y1-1])

 

 

 

---

(위) 두 번째 방법/ (아래) 첫 번째 방법

무려 거의 4배 차이가 났습니다.