[11660] 구간 합 구하기5 #python

백준 11660번 구간 합 구하기

내가 푼 답 ⇒ 시간 초과!

n, m = map(int, input().split())
square = []
for i in range(n):
    square.append(list(map(int, input().split())))

for i in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    data = list(map(lambda x: sum(x[y1-1:y2]), square[x1-1:x2]))
    print(sum(data))

정답

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
square = [list(map(int,input().split())) for _ in range(n)]
for k in range(2):
    for i in range(n):
        if k == 1 and i == 0:
            continue
        for j in range(n):
            if k == 0:
                if j == 0:
                    continue
                square[i][j] += square[i][j-1]
            else:
                square[i][j] += square[i-1][j]


for i in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    if x1 == 1 and y1 == 1:
        print(square[x2-1][y2-1])
    elif x1 == 1:
        print(square[x2-1][y2-1] - square[x2-1][y1-2])
    elif y1 == 1:
        print(square[x2-1][y2-1] - square[x1-2][y2-1])
    else:
        print(square[x2-1][y2-1] - square[x1-2][y2-1] - square[x2-1][y1-2] + square[x1-2][y1-2])

정답 포인트는 값을 포문을 돌려가며 구하는게 아니라, 테이블 자체의 각 값을 위치 별 합을 구해서 더하기로 계산으로 끝냄

내가 푼 식이 시간 초과한 이유를 살펴보자

조건 :

• 시간 제한 1초, 메모리 제한 256M
• 1≤N≤1,024, 1≤M≤100,000

내가 푼 식 시간 복잡도:

• 첫 번째 for 문 : N
• 두 번째 for 문 : M * N
• 시간 복잡도 : O(M*N) , 최댓값 : 100,000 * 1,024 = 1억

정답 문제 시간 복잡도:

• 첫 번째 for문 : N
• 두 번째 for문 : 2 * N * N
• 3번째 for문 : M
• 시간 복잡도 : O(N**2), 최댓값 : 1024 * 1024 = 백만