🟩 [백준] [Python] [Silver1] 11660번_구간 합 구하기 5

문제

https://www.acmicpc.net/problem/11660

풀이

# 백준 11660번 문제 - 구간 합 구하기 5
n, m = map(int, input().split())

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

for i in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    result = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]
    print(result)

처음에 이해를 하는데 애를 먹어서 다른 풀이를 찾아보았다. 

가장 쉽게 이해할 수 있었던 풀이는 영역을 나누어서 x1, x2, y1, y2 좌표를 보고 공통되는 부분을 다시 더해주는 풀이었다. 

DP 문제는 많이 풀어봐야겠다. 

** sys 모듈을 사용하지 않으면 시간초과가 나게 된다.