문제 링크

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

문제 설명

• board 가 주어진다
• 특정 좌표 y1, x2 부터 y2, x2 까지의 합을 출력

풀이

• 처음에 그때 그때 합을 구해봤지만 당연하게도 시간초과
• DP로 (0, 0)부터 특정 좌표까지의 합을 모두 저장
• 범위가 주어졌을 때 다음처럼 값을 계산해 출력
  

코드

import sys


def init():
    n, m = map(int, ipt().split())
    board = [tuple(map(int, ipt().split())) for _ in range(n)]
    quest_list = [tuple(map(int, ipt().split())) for _ in range(m)]
    dp = [[0] * n for _ in range(n)]
    dp[0][0] = board[0][0]
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + board[0][j]
    for i in range(1, n):
        dp[i][0] = dp[i-1][0] + board[i][0]
    return n, quest_list, board, dp


ipt = sys.stdin.readline
opt = sys.stdout.write
n, quest_list, board, dp = init()
for i in range(1, n):
    for j in range(1, n):
        dp[i][j] = board[i][j] +  dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
for y1, x1, y2, x2 in quest_list:
    y1, x1, y2, x2 = y1-1, x1-1, y2-1, x2-1
    result = dp[y2][x2]
    if y1-1 >= 0:
        result -= dp[y1-1][x2]
    if x1-1 >= 0:
        result -= dp[y2][x1-1]
    if y1-1 >= 0 and x1-1 >= 0:
        result += dp[y1-1][x1-1]
    opt(f'{result}\n')