[백준 파이썬] 11660 구간 합 구하기5

 

11660번: 구간 합 구하기 5

문제

 

배열이 주어진 후 한 지점부터 특정 지점까지의 합을 구하는 문제이다.

---

 

아이디어

(1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 이라는 조건이 있기 때문에 무턱대고 반복문을 이용해 합을 구하면 시간초과가 난다.

따라서 구간합을 이용해서 효율적으로 계산해야한다.

 

x1,y1 부터 x2,y2까지의 구간합은 다음과 위와 같이 구할 수 있다. 따라서 모든 구간에서의 누적합을 구해놓은 후 필요한 영역의 구간합을 위와같이 계산하면 된다.

---

풀이

for i in range(1, N+1):
    for j in range(1, N+1):
        dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + matrix[i-1][j-1]

모든 구간의 누적합을 구하는 코드를 작성하였다.

 

for k in range(M):
    x1, y1, x2, y2 = map(int, input().split())

    res = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]
    print(res)

x1 y1, x2 y2 의 값을 입력받은 후 해당 구간의 구간합을 구한 후 출력하였다.

---

코드

import sys
input = sys.stdin.readline
N, M = map(int, input().split())

matrix = [list(map(int, input().split())) for _ in range(N)]

dp = [[0] * (N+1) for _ in range(N+1)]

for i in range(1, N+1):
    for j in range(1, N+1):
        dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + matrix[i-1][j-1]

for k in range(M):
    x1, y1, x2, y2 = map(int, input().split())

    res = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]
    print(res)