11660. 구간 합 구하기 5

문제

백준 11660번 구간 합 구하기 5

---

풀이

표에서 주어진 구간의 값들의 총합을 구하는 문제니까 다이나믹 프로그래밍으로 빠르게 값을 계산할 수 있도록 한다.

표를 board로 입력받을건데 편의상 0번 인덱스에 0을 넣어주기 위해 아래와 같이 입력받았다.

board = [[0] * (n+1) for _ in range(n+1)]
for i in range(1, n+1):
    board[i][1:] = list(map(int, sys.stdin.readline().split()))

리스트 dp 역시 (n+1) * (n+1) 크기로 만들고 값을 계산한다.

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-1][j] + dp[i][j-1] - dp[i-1][j-1] + board[i][j]

dp에 미리 구해놓은 누적합을 이용해서 m개의 줄에서 들어오는 구간들에 대해 구간합을 출력해준다.

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])

전체코드

import sys

n, m = map(int, sys.stdin.readline().split())
board = [[0] * (n+1) for _ in range(n+1)]
for i in range(1, n+1):
    board[i][1:] = list(map(int, sys.stdin.readline().split()))

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-1][j] + dp[i][j-1] - dp[i-1][j-1] + board[i][j]

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])