BAEKJOON (Python)/Prefix Sum Algorithm
BAEKJOON_2167 "2차원 배열의 합" PYTHON
RiLLa_0511
2023. 3. 30. 15:16
728x90
[백준] 2167번 Python 파이썬
https://www.acmicpc.net/problem/2167
2167번: 2차원 배열의 합
첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는
www.acmicpc.net
11660 문제와 유사하여 행렬의 크기 등만 조금 수정하였다.
아래 사이트 참고!
https://rilla0511.tistory.com/95
BAEKJOON_11660 "구간 합 구하기 5" PYTHON
[백준] 11660번 Python 파이썬 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의
rilla0511.tistory.com
import sys
n, m = map(int,sys.stdin.readline().split())
tb = [[0 for j in range(m)] for i in range(n)]
for i in range(n):
lt = list(map(int, sys.stdin.readline().split()))
for j in range(m):
tb[i][j] = lt[j]
st = [[0 for j in range(m)] for i in range(n)]
for i in range(n):
for j in range(m):
if i == 0 and j == 0:
st[i][j] = tb[i][j]
elif i == 0:
st[i][j] = st[i][j-1] + tb[i][j]
elif j == 0:
st[i][j] = st[i-1][j] + tb[i][j]
else:
st[i][j] = st[i-1][j] + st[i][j-1] - st[i-1][j-1] + tb[i][j]
answer = []
for i in range(int(sys.stdin.readline())):
x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
if (x1 == x2 and y1 == y2):
answer.append(tb[x2-1][y2-1])
elif x1 == 1 and y1 == 1:
answer.append(st[x2-1][y2-1])
elif x1 == 1:
answer.append(st[x2-1][y2-1] - st[x2-1][y1-2])
elif y1 == 1:
answer.append(st[x2-1][y2-1] - st[x1-2][y2-1])
else:
answer.append(st[x2-1][y2-1] - st[x1-2][y2-1] - st[x2-1][y1-2] + st[x1-2][y1-2])
for i in answer:
print(i)
혼자 공부하며 올리는 블로그입니다. 틀린 내용은 댓글 남겨주시면 감사하겠습니다.
728x90