사용 언어 - 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)
레퍼런스
'Algorithm > 구현' 카테고리의 다른 글
| [백준] 3273번 두 수의 합 (투포인터 문제) (0) | 2023.11.02 |
|---|---|
| [백준] 3020번 개똥벌레 (1) | 2023.10.24 |
| [백준] 2304번 창고 다각형 (1) | 2023.10.23 |
| [백준] 1912번 연속합 (0) | 2023.10.23 |
| [백준] 2559번 수열 (1) | 2023.10.23 |
댓글