[백준/파이썬] 15724 주지수

#문제링크

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

15724번: 주지수

#나의풀이

import sys

if __name__=="__main__":
    N, M = map(int, sys.stdin.readline().split())
    board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

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

    T = int(sys.stdin.readline())

    for _ in range(T):
        s_x, s_y, e_x, e_y = map(int, sys.stdin.readline().split())
        answer = sum(board[e_x-1][s_y-1:e_y])
        if s_x > 1:
            answer -= sum(board[s_x-2][s_y-1:e_y])
        print(answer)

#해설

간단해보이지만 누적합 문제로 어떻게 누적합을 할것인가를 잘 생각해야하는 문제로

지금까지 누적합을 풀었을때 가로를 기준으로 누적합을 풀어 처음에 풀었다가 시간초과가 떠버렸고 세로로 누적합을 하면 시간을 많이 줄일수 있었다.

 

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

 

세로 기준으로 누적합을 만들어야해서 0번째 row는 건너뛰고 1번째 row부터 끝까지 진행한다.

 

    for _ in range(T):
        s_x, s_y, e_x, e_y = map(int, sys.stdin.readline().split())
        answer = sum(board[e_x-1][s_y-1:e_y])
        if s_x > 1:
            answer -= sum(board[s_x-2][s_y-1:e_y])
        print(answer)

answer에 끝행에 시작 y부터 끝 y 까지 각 열에 누적합을 해준것을 더해준다.

이후 시작이 행의 값 1(입력값이 1부터이므로 0을 의미함)보다 크다면 시작전에 누적된 부분은 빼줘야 하므로 값을 다시 빼주었다.