[파이썬]백준 2167 - 2차원 배열의 합
2167 - 2차원 배열의 합
부분합을 구하는 문제인데 dp를 이용해서 풀었습니다.
우선 dp 배열의 각 위치에 각 부분합들을 모두 기록을 하고 각각의 좌표(x, y), (i, j)가 들어온다면 dp[x][y] - dp[i-1][y] - dp[x][j-1] + dp[i-1][j-1]을 해주면 됩니다.
소스코드
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
arr = [list(map(int, input().split())) for i in range(n)]
k = int(input())
dp = [[0] * (m+1) for i in range(n+1)]
for i in range(1, n+1):
for j in range(1, m+1):
dp[i][j] = arr[i-1][j-1] + dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]
for i in range(k):
i, j, x, y = map(int, input().split())
print(dp[x][y] - dp[x][j-1] - dp[i-1][y] + dp[i-1][j-1])
Author And Source
이 문제에 관하여([파이썬]백준 2167 - 2차원 배열의 합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@turret1234/파이썬백준-2167-2차원-배열의-합저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)