[백준/Python] 2167 2차원 배열의 합

※ Python3으로 시간초과 뜨지 않고 푸는 법은 아래에 정리해두었습니다!

 

 

python3으로 했을 땐 시간초과가 떠서 PyPy3으로 돌렸더니 성공했다.

이중 for문 때문에 그런 거 같긴 한데, python3으로도 성공할 수 있는 방법을 찾으면 업데이트 하겠음..

 

처음에는 (1, 1)부터 (2, 3) 까지 더한다고 할 때,

(1, 1) + (1, 2) + (1, 3) + (2, 1) + (2, 2) + (2, 3) 인 줄 알았는데,

(1, 1) + (2, 1) + (1,2) + (2, 2) + (1, 3) + (2, 3) 순으로 더해야 한다!!!!!!!!

그래서 while문 안에서 이중 for문을 돌릴 때,

lst[x][y]에서 첫번째 for문은 y를, 두번째 for문은 x를 증가시켜야함

 

from collections import deque
N, M = map(int, input().split())
lst = []
start, end = deque(), deque()
for _ in range(N):
    lst.append(list(map(int, input().split())))
K = int(input())
for _ in range(K):
    i, j, x, y = list(map(int, input().split()))
    start.append((i, j))
    end.append((x, y))

while start:
    answer = 0
    i, j = start.popleft()
    x, y = end.popleft()
    for a in range(j, y+1):
        for b in range(i, x+1):
            answer += lst[b-1][a-1]
    print(answer)

풀이과정

1. i, j, x, y를 각각 start, end에 좌표 형태로 append

1-1. 처음 넣었던 값부터 계산해야하기 때문에 popleft를 해야함 → deque()로 start, end 만듦

 

2. 순서대로 더해서 정답을 구함

 

---

Python3으로 시간초과 나지 않고 푸는 방법!!

 

가장 중요한 알고리즘은 "누적합" 알고리즘

누적합은 합 배열을 이용하여 시간복잡도를 O(n)에서 O(1)로 줄이기 위해 사용하는 알고리즘!

 

2차원 배열의 누적합을 구하는 공식은:

A[i][j] = A[i][j] + A[i][j-1] + A[i-1][j] -A[i-1][j-1]

 

A[i][j]부터 A[x][y]까지의 누적합을 구하는 공식:

A[x][y] - A[i-1][y] - A[x][j-1] + A[i-1][j-1]

 

이 것을 이용하여 풀면 아래와 같은 코드가 나온다

N, M = map(int, input().split())
lst = [[0]*(M+1)] + [[0] + list(map(int,input().split())) for _ in range(N)]

for n in range(1, N+1):
    for m in range(1, M+1):
        lst[n][m] = lst[n][m]+ lst[n][m-1] + lst[n-1][m] - lst[n-1][m-1]

for _ in range(int(input())):
    i, j, x, y = map(int, input().split())
    print(lst[x][y] - lst[i-1][y] - lst[x][j-1] + lst[i-1][j-1])