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

문제바로가기

생각보다 문제 푸는데 오래 걸렸는데 그 이유는 문제를 잘못이해했기 때문이다. 그냥 i~x, j~y까지를 계산하면 되는데 나는 더 꼬아서 연속된 값을 찾는다고 생각했다. 예를 들어 i가 1이고 x가 3이면 2행은 전부 포함되는 것이다. 당연하게도.. 아니다!

N, M = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]

def matrix_sum(i, j, x, y):
    total = 0
    for row in range(i, x + 1):
        for col in range(j, y + 1): 
            total += matrix[row][col]
    return total

T = int(input())
for _ in range(T):
    i, j, x, y = map(int, input().split())
    print(matrix_sum(i - 1, j - 1, x - 1, y - 1))

제일 간단한 방식으로 이렇게 풀었지만, prfix sum으로 푸는 것이 더 효율이 좋다.