15724. 주지수

문제

백준 15724번 주지수

---

풀이

처음엔 무작정 "dy[x2][y2] 출력하면 끝나는 거 아니야???" 라고 생각하고 채점돌렸더니 틀렸습니다~~

뭐가 잘못된지 몰랐다. 그리고 x1, y1을 쓸데없이 왜주나 생각했다.

역시 그냥 주어지는 건 없다. 항상 모든 것엔 이유가 있다;;

무슨 케이스를 넣어볼지 생각하다가 불현듯 깨달았다.
x1, y1이 1, 1부터 시작하지 않을 수도 있는거였다.

역시나 다른 값 넣어보니 손으로 구한 답과 다른 답이 나왔다.

먼저 인덱스 접근 편의상 board의 0행, 0열에 0을 넣어줬다.

board.insert(0, [0]*(m+1))
for i in range(n+1): board[i].insert(0, 0)

이제 리스트 dy에 board[1][1]부터 board[n][m]까지 누적합을 구해 저장하는데,

[1][1] ~ [i][j]까지의 누적합을 구할 때 이전 행, 이전 열의 정보를 활용한다.

그림으로 나타내면 다음과 같다.

board에서 현재 위치 + 이전 행까지의 누적합 + 이전 열까지의 누적합 - 중복된 값 = 현재위치까지의 누적합

그리고 이제 입력된 x1, y1, x2, y2 구역에 따른 값을 출력한다.

x1, y1 = 2, 2이고 x2, y2 = 4, 4라고 가정했을 때
dy[x2][y2]에는 [1][1] ~ [4][4]까지의 누적합이 저장되어있다.
하지만 1행[1][1] ~ [1][4]과 1열[1][1] ~ [4][1]은 필요없으므로 빼주고 중복해서 뺀 [1][1]값을 더해주면 [x1][y1] ~ [x2][y2]까지의 누적합만 구할 수 있다.

n, m = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
board.insert(0, [0]*(m+1))
for i in range(n+1): board[i].insert(0, 0)

dy = [list(0 for _ in range(m+1)) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        dy[i][j] = dy[i-1][j] + dy[i][j-1] - dy[i-1][j-1] + board[i][j]

k = int(sys.stdin.readline())
for _ in range(k):
    x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
    print(dy[x2][y2] - dy[x1-1][y2] - dy[x2][y1-1] + dy[x1-1][y1-1])