Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- queue
- backtracking
- segment-tree
- bitmask
- implementation
- PS
- knapsack
- Greedy
- lazy-propagation
- Dijkstra
- DP
- stack
- Python
- Constructive
- Prefix-Sum
- ad_hoc
- sliding-window
- C++
- BFS
- number_theory
- floyd_warshall
- priority_queue
- C
- string
- Binary-Search
- java
- Sort
- bruteforcing
- codeup
- math
Archives
- Today
- Total
공작소
[ BOJ ] 11660 : 구간 합 구하기 5 ( SILVER 1 ) / Python 본문
문제 링크 : https://www.acmicpc.net/problem/11660
문제
N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.
예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.
1 | 2 | 3 | 4 |
2 | 3 | 4 | 5 |
3 | 4 | 5 | 6 |
4 | 5 | 6 | 7 |
여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.
표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.
입력
첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)
출력
총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.
풀이 과정
2차원 누적 합 배열을 만들고 (x1, y1)부터 (x2, y2)까지 합을 한번에 구한다.
import sys
input = sys.stdin.readline
n, m = map(int, input().rstrip().split())
arr = [list(map(int, input().rstrip().split())) for _ in range(n)]
sums = [[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, n+1):
sums[i][j] = sums[i-1][j] + sums[i][j-1] + arr[i-1][j-1] - sums[i-1][j-1]
for i in range(m):
x1, y1, x2, y2 = map(int, input().rstrip().split())
print(sums[x2][y2] - sums[x1-1][y2] - sums[x2][y1-1] + sums[x1-1][y1-1])
'Problem Solving > BOJ' 카테고리의 다른 글
[ BOJ ] 11659 : 구간 합 구하기 4 ( SILVER 3 ) / Python (0) | 2024.04.14 |
---|---|
[ BOJ ] 2157 : 여행 ( GOLD 4 ) / Python (1) | 2024.03.22 |
[ BOJ ] 16936 : 나3곱2 ( GOLD 5 ) / Python (0) | 2024.03.22 |
[ BOJ ] 17615 : 볼 모으기 ( SILVER 1 ) / Python (0) | 2024.03.22 |
[ BOJ ] 6236 : 용돈 관리 ( SILVER 2 ) / Python (0) | 2024.03.22 |