인프런 커뮤니티 질문&답변

안녕하세요,이 문제에서 prefix 를 만드실 때 처음부터 5*5 리스트를 만드셨는데 이 아이디어는 어떻게 떠올리신 건지 궁금합니다. 저 방식이 누적합 문제를 풀 때 일반적으로 사용되는 방식인가요?저같은 경우에는 4*4형식으로 만들어서 코드를 작성하였는데 이렇게 하니 답은 맞는데 시간 초과가 뜨네용

n, m = map(int, input().split())

box2 = []
for _ in range(n):
    box2.append(list(map(int, input().split())))

for i in range(n):
    for j in range(n):
        if i - 1 >= 0:
            box2[i][j] += box2[i - 1][j]
        if j - 1 >= 0:
            box2[i][j] += box2[i][j - 1]
        if i - 1 >= 0 and j - 1 >= 0:
            box2[i][j] -= box2[i - 1][j - 1]

# 쿼리 처리
for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    answer = box2[x2 - 1][y2 - 1]
    if x1 - 2 >= 0:
        answer -= box2[x1 - 2][y2 - 1]
    if y1 - 2 >= 0:
        answer -= box2[x2 - 1][y1 - 2]
    if x1 - 2 >= 0 and y1 - 2 >= 0:
        answer += box2[x1 - 2][y1 - 2]
    print(answer)