백준 2167

# 2167

import sys

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

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

# print(ary)
    
k = int(sys.stdin.readline())
for _ in range(k):
    i, j, x, y = map(int, sys.stdin.readline().split())
    result = 0

    for u in range(i - 1, x):
        for v in range(j - 1, y):
            result += ary[u][v]

    print(result)

시간 초과!

주어진 2차원 배열의 (i, j)부터 (x, y)까지의 합을 구하는 것이므로,
더하고자 하는 부분은 항상 직사각형 형태이다.

이 사실을 이용하면..
리스트 슬라이싱을 통해 위 코드의 시간 초과 원인인 이중 for문을 없앨 수 있다.

코드(정답)는 다음과 같다.

# 2167

import sys

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

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

# print(ary)
    
k = int(sys.stdin.readline())
for _ in range(k):
    i, j, x, y = map(int, sys.stdin.readline().split())

    result = 0
    for col in range(i - 1, x):
        result += sum(ary[col][j - 1:y])

    print(result)

기타

다른 분들의 풀이를 찾아보니, DP로 푼 풀이가 많다.
그리고 내용을 훑어보니 알고리즘 수업에서 봤던 DP 유도 과정을 떠올릴 수 있는 문제인 것 같아 DP로 다시 풀어봐야겠다.