[백준] 11660번 구간 합 구하기 5

💡문제접근

• 해당 문제는 직접 좌표의 값을 찾아 계산을 하게 된다면 시간초과(TLE)가 100% 발생하게 된다. 이 문제는 누적 합 개념을 이용해야하는데 2차원 누적 합에 대한 공부가 되어있지않아 접근이 어려웠다. 2차원 배열의 구간 합에 대해서 잘 정리해놓은 포스팅을 참고해서 공부한 다음 이 문제를 도전했다.

💡코드(메모리 : 106008KB, 시간 : 1116ms)

import sys
input = sys.stdin.readline

N, M = map(int, input().strip().split())
board = [list(map(int, input().strip().split())) for _ in range(N)]
# 2차원 배열의 누적 합을 구하기 위해 만든 배열
sum_board = [[0] * (N+1) for _ in range(N+1)]

for i in range(1, N+1):
    for j in range(1, N+1):
        sum_board[i][j] = sum_board[i][j-1] + sum_board[i-1][j] - sum_board[i-1][j-1] + board[i-1][j-1]

for _ in range(M):
    x1, y1, x2, y2 = map(int, input().strip().split())
    print(sum_board[x2][y2] - sum_board[x2][y1-1] - sum_board[x1-1][y2] + sum_board[x1-1][y1-1])

💡소요시간 : 40m