#11660

1차 시도

N, M = map(int, input().split())

inputMap = []
for i in range(N):
    inputMap.append(list(map(int, input().split())))

totalList = []

for j in range(M):
    x1, y1, x2, y2 = map(int, input().split())
    totalList.append([x1, y1, x2, y2])
# print("totalList = ", totalList)

answerList = []

for i in range(M):
    sumVal = 0
    for rowIdx in range(totalList[i][1]-1, totalList[i][3]):
        for colIdx in range(totalList[i][0]-1, totalList[i][2]):
            # print("row : ", rowIdx, "col : ", colIdx)
            sumVal += inputMap[rowIdx][colIdx]
    answerList.append(sumVal)

for i in range(M):
    print(answerList[i])

시간 초과

입력받은 값을 이용해서 맵을 순회하는 방법이다. 너무 쉽게 풀려서 이게 어떻게 실버1이지? 라는 생각을 잠깐 했다. 역시나 이렇게 푸는 게 아니였다.

x1, y1, x2, y2 가 2, 2, 3, 4 라고 했을 때
y1에서 x1 - x2 까지 구하고 하나씩 내려가면서 y2까지 보는 방법이다.

무조건 한번 씩은 봐야하는 거 아닌가? 라는 생각을 했다.

for loop 의 깊이가 쓸떼없이 깊다 생각하여 깊이를 조금 줄이고 재시도

2차 시도

N, M = map(int, input().split())

inputMap = []
for i in range(N):
    inputMap.append(list(map(int, input().split())))

answerList = []

for i in range(M):
    x1, y1, x2, y2 = map(int, input().split())

    sumVal = 0
    for rowIdx in range(y1-1, y2):
        for colIdx in range(x1-1, x2):
            sumVal += inputMap[rowIdx][colIdx]
    answerList.append(sumVal)

for i in range(M):
    print(answerList[i])

=> 시간 초과

입력을 받을 때도 시간을 많이 줄일 수 있다고 하여

from sys import stdin
n = int(stdin.readline())

이거로 재시도

3차 시도

from sys import stdin
N, M = map(int, stdin.readline().split())

inputMap = []
for i in range(N):
    inputMap.append(list(map(int, input().split())))

answerList = []

for i in range(M):
    x1, y1, x2, y2 = map(int, input().split())

    sumVal = 0
    for rowIdx in range(x1-1, x2):
        for colIdx in range(y1-1, y2):
            sumVal += inputMap[rowIdx][colIdx]
    answerList.append(sumVal)

for i in range(M):
    print(answerList[i])

=> 시간 초과
(심지어 3% 에서 시간 초과가 뜬다 => 100개 TC 중에 3개만 통과)

뭔가 엄청나게 잘못된, 아직도 모르고 있는 뭔가가 분명히 있다는 걸 인지하고 코드 다 지우고 다시 풀기

어차피 합만 구하면 돼.
=> 직접 한칸 한칸 다 보지말고 미리 그 Row의 합을 다 구해놓고? 범위에 안맞는 인덱스의 값만 빼주면 돼 그럼 범위 안에 있는 인덱스를 전부 방문하는 것보다는 방문 횟수가 훨씬 줄어들겠지 (숫자가 클수록 더)

4차 시도

from sys import stdin
N, M = map(int, stdin.readline().split())

inputMap = []
for i in range(N):
    oneRow = list(map(int, input().split()))
    oneRow.append(sum(oneRow))
    inputMap.append(oneRow)

# print("inputMap = ", inputMap)

answerList = []

for i in range(M):
    x1, y1, x2, y2 = map(int, input().split())
    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1
    sumVal = 0

    for row in range(x1, x2+1):
        # print("원래 로우의 합 = ", inputMap[row][-1])
        rowSum = inputMap[row][-1] 
        for col in range(0, N):
            # print("row = ", row, " col = ", col)
            if col < y1 or col > y2:
                # print("row = ", row, " col = ", col, " 뺄 값 = ", inputMap[row][col])
                rowSum -= inputMap[row][col]

        # print("이번 로우에서의 최종 값은 ? ", rowSum)
        sumVal += rowSum
        # print("더해지고 나서 값은 ? ", sumVal)
    answerList.append(sumVal)
    # print("answerList = ", answerList)
        
for i in range(M):
    print(answerList[i])

=> 시간 초과

안된다 그냥 답지 보자

prefix sum (구간 합)

가장 쉬운 방법은 반복문으로 해당하는 값들을 일일이 순회하면서 더하는 것이다. 이게 바로 내가 이 때까지 삽질했던 풀이이다. 하지만 여러 구간 합을 구해야 할 경우 이러한 방법은 비효율적이다. 비효율적인게 아니라 시간초과가 떠서 문제를 맞출 수가 없다. 이때 사용할 수 있는 것이 바로 구간 합(prefix sum)이다.

구간 합은 어떤 수열에서 해당 인덱스까지의 수열의 전체 합을 의미한다.
예를 들어, [10, 20, 30, 40, 50]의 구간 합은 [10, 30, 60, 100, 150]이다.

위 문제는 이 구간 합 개념을 2차원 배열에 적용하여 해결할 수 있다. 기본 구간 합이 수열의 처음 수부터 해당 인덱스의 수까지의 합을 저장한다면, 2차원 배열에서는 1행 1열부터 x행 y열까지의 수들의 합을 prefix_sum[x][y]에 저장할 수 있다.

(3, 3)부터 (4, 5)까지의 합을 구하는 예시를 생각해보자. 위 그림에서 구해야 할 값은 D의 값(합)이다. prefix_sum[4][5]은 A ~ D를 모두 더한 값과 같다(A+B+C+D) 여기에서 A, B, C의 값을 빼면 구하고자 하는 D의 값이 남는다.

prefix_sum[2][5]는 A + B이고, prefix_sum[4][2]는 A + C이다. A ~ D의 합에서 이 둘을 빼면 D - A가 된다. A의 값은 prefix_sum[2][2]이므로 다시 이 값을 더하면 구하고자 하는 D의 값이 된다.

출처 - ready2start.log

정답 코드

from sys import stdin

N, M = map(int, stdin.readline().split())

# inputMap = []
# for i in range(N):
#     inputMap.append(list(map(int, stdin.readline().split())))
# 이거 대신에 밑에 코드

inputMap = [[0] * (N+1)] 
# 첫 번째 로우만 먼저 만들어주고 => 어차피 안쓰는 로우

for _ in range(N):
    oneRow = [0] + list(map(int, stdin.readline().split()))
    # [0] 먼저 넣어두고 그 뒤로 추가, 어차피 0번 컬럼은 안쓰니까
    inputMap.append(oneRow)
# print(inputMap)
# 입력값이 1부터 시작하므로 (배열의 시작은 0이잖아) N+1 만큼 만들어준다.
# 나는 이전에 입력값에다가 -1 을 해줘서 풀이를 진행했는데 이게 더 편할 수 있겠다.
# 잘 익혀뒀다가 다음번에 써먹자 (컬럼, 로우 1부터 시작할 경우)

# 1. 행 별로 더하기
for i in range(1, N + 1):
    for j in range(1, N):
        inputMap[i][j + 1] += inputMap[i][j]

# 2. 열 별로 더하기
for j in range(1, N + 1):
    for i in range(1, N):
        inputMap[i + 1][j] += inputMap[i][j]

# N까지 합 다 만들어놨음 
# 이제 빼줄 차례

for _ in range(M):
    x1, y1, x2, y2 = map(int, stdin.readline().split())
    # (x1, y1)에서 (x2, y2)까지의 합
    # p[x2][y2] - p[x1 - 1][y2] - p[x2][y1 - 1] + p[x1 - 1][y1 - 1]
    print(inputMap[x2][y2] - inputMap[x1 - 1][y2] - inputMap[x2][y1 - 1] + inputMap[x1 - 1][y1 - 1])