bj 구간합구하기5

목차

내 코드 

# 코드보기

java

닫기 줄바꿈

import sys
n,m = map(int,sys.stdin.readline().split())
dp = [ [0] * (n + 1) for _ in range(n + 1)]

numbers = [0]*n
for i in range(n):
​​​​numbers[i] = list(map(int,sys.stdin.readline().split()))

# 누적 합
for i in range(1, n + 1):
​​​​for j in range(1, n +1 ):
​​​​​​​​dp[i][j] = numbers[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] 
​​​​​​​
for _ in range(m):
​​​​x1,y1,x2,y2 = map(int, sys.stdin.readline().split())
​​​​print(dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1])

# 접기

 

다른사람풀이

- 속도 면에서 내코드보다 조금 더 빠름

# 코드보기

java

닫기 줄바꿈

import sys
n, m = map(int, input().split())
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(1, n+1):
​​​​sumRow = 0
​​​​j = 1
​​​​for num in map(int, sys.stdin.readline().split()):
​​​​​​​​dp[i][j] = dp[i-1][j] + sumRow + num
​​​​​​​​sumRow += num
​​​​​​​​j += 1
​​​​​​​
for _ in range(m):
​​​​i1, j1, i2, j2 = map(int, sys.stdin.readline().split())
​​​​print(dp[i2][j2] - dp[i2][j1-1] - dp[i1-1][j2] + dp[i1-1][j1-1])

# 접기