백준 11660번: 구간 합 구하기 5 (Python)

접근

https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

문제의 제목에서 알 수 있 듯, 구간합을 이용하여 푸는 문제였습니다. arr 을 만들어 arr[i][j] 에는 (1, 1) 부터 (i, j) 까지 사각형에 들어간 수의 합을 저장해주면 됩니다.

구간 합을 빠르게 구하는 문제이기 때문에 입력이 많이 주어질 것이라고 예상하여 input 대신 sys.stdin.readline 을 사용해주었습니다. 예상대로 input 을 쓰면 시간 초과가 발생하게 됩니다.

코드

import sys

N, M = map(int, sys.stdin.readline().split(" "))
arr = [[0] * (N + 1)]
for _ in range(N):
    arr.append([0] + list(map(int, sys.stdin.readline().split(" "))))
sum_arr = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    tmp_sum = 0
    for j in range(1, N + 1):
        tmp_sum += arr[i][j]
        sum_arr[i][j] = tmp_sum + sum_arr[i - 1][j]


def prefixSum(x1, y1, x2, y2):
    return sum_arr[x2][y2] - sum_arr[x1 - 1][y2] - sum_arr[x2][y1 - 1] + sum_arr[x1 - 1][y1 - 1]


for t in range(M):
    print(prefixSum(*map(int, sys.stdin.readline().split(" "))))

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!