Algorithm/구현

[백준] 11600번 구간 합 구하기 5

HANNI하니 2023. 10. 24. 15:58

사용 언어 - Python3

문제 -  구간 합 구하기 5 (실버 1)

 

11660번: 구간 합 구하기 5

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

www.acmicpc.net

 

정답

누적된 숫자들의 prefix 2차원 형태 (정답 맞춘 여부 X)

1. input

graph[y][x]

prefix도 [n+1][n+1] 배열로 만들기

 

2. 누적합 구할때 규칙 찾기

 

3. output

새로운 y1,x1,y2,x2 입력될 때마다 answer print 하기

import sys
input = sys.stdin.readline
n, m  = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(n)]
prefix = [[0 for _ in range(n+1)] for _ in range(n+1)]

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

for _ in range(m):
    y1, x1, y2, x2 = map(int,input().split())

    answer = prefix[y2][x2] - prefix[y2][x1-1] - prefix[y1-1][x2] + prefix[y1-1][x1-1]
    print(answer)

 

 

 

레퍼런스