[누적합] 백준 11660번: 구간 합 구하기 5 / 실버 1

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

11660번: 구간 합 구하기 5

import sys
n, m = map(int, input().split())
table = []
for i in range(n):
    row = list(map(int, sys.stdin.readline().split()))
    for j in range(1, n):
        row[j] += row[j-1]
    table.append(row)

for x in range(1, n):
    for y in range(n):
        table[x][y] += table[x-1][y]

for i in range(m):
    x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
    init = table[x2-1][y2-1]
    if x1 != 1 and y1 != 1:
        table[x2 - 1][y2 - 1] += table[x1 - 2][y1 - 2]
    if x1 != 1:
        table[x2 - 1][y2 - 1] -= table[x1-2][y2-1]
    if y1 != 1:
        table[x2 - 1][y2 - 1] -= table[x2-1][y1-2]
    print(table[x2-1][y2-1])
    table[x2-1][y2-1] = init

이 문제가 오래 걸린 이유는 시간 초과 때문인데 그 밖에 여러가지 문제점이 있었다.

 

1. 푸는 방식이 바로 떠오르지 않음 -> 어떤 방법이 제일 효율적일까 바로 떠오르지 않음

 

2. 제일 마지막 반복문 도는 부분에서 여러 케이스를 나눠서 했는데 이부분이 엄청 헷갈림. 이 여러개 if문 확인을 안하게 할 수 있는 방법이 있는데, 테이블을 만들때 n*n이 아니라 n+1*n+1로 만들어서 첫째 열, 행을 0으로 초기화 해주면 된다. 그럼 인덱스가 -1이 돼서 마지막 배열값을 읽어오는 불상사를 사전에 방지할 수 있다.