백준 11660번: 구간 합 구하기 5
구간 합 구하기 5
아이디어
각 행별로 합을 기록한다. 1 2 3 4 -> 1 3 6 10
그리고 각 열별로 합을 기록한다.
이렇게 만들어진 2차원 배열에서 (r, c)에 적힌 숫자는 (1, 1)부터 (r, c)까지 커다란 직사각형에 적힌 모든 숫자의 합이다. 이를 잘 이용하면 원하는 범위 (파란색 직사각형)의 합을 구할 수 있다. (그림 참고)
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
arr = [[0] + list(map(int, input().split())) for _ in range(N)]
arr.insert(0, [0] * (N + 1))
for row in range(N + 1):
for col in range(1, N + 1):
arr[row][col] += arr[row][col - 1]
for col in range(N + 1):
for row in range(1, N + 1):
arr[row][col] += arr[row - 1][col]
for _ in range(M):
r1, c1, r2, c2 = map(int, input().split())
ans = arr[r2][c2] - arr[r1 - 1][c2] - arr[r2][c1 - 1] + arr[r1 - 1][c1 - 1]
print(ans)
여담
input = sys.stdin.readline 이거 없으면 안됨
Author And Source
이 문제에 관하여(백준 11660번: 구간 합 구하기 5), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ks1ksi/백준-11660번-구간-합-구하기-5-y8lg6w0o저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)