Algorithm (PS)

[백준] 15724 주지수 python 풀이

minjiwoo 2022. 11. 18. 18:10
728x90

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

 

15724번: 주지수

네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은

www.acmicpc.net

누적합 문제이다 

백준 11660 구간합 구하기 5 문제를 지난주에 풀었어서 복습하는 차원으로 풀었다. 

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

 

11660번: 구간 합 구하기 5

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네

www.acmicpc.net

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
array = [[0]*(m+1)]
for _ in range(n):
    array.append([0]+list(map(int, input().split())))

# 누적합 구하기
for i in range(1, n+1):
    for j in range(1, m):
        array[i][j+1] += array[i][j]

for j in range(1, m+1):
    for i in range(1, n):
        array[i+1][j] += array[i][j]

k = int(input())
for _ in range(k):
    x1, y1, x2, y2 = map(int, input().split())
    result = array[x2][y2] - array[x1-1][y2] - array[x2][y1-1] + array[x1-1][y1-1]
    print(result)
728x90