처음에는 범위를 제대로 안보고 이중 for문을 통해 구현 하였더니
당연히 시간초과가 발생했다.
어떻게 해야할지 방법을 찾다가 dp를 통해 문제를 해결하면 되겠다고 막연히 생각은 했으나 단순이 dp[x2][y2]-dp[x1][y1] 을 해보다가 좀 더 식을 상세하게 세워야지 문제를 해결 할 수 있다는 것을 깨달았다.
일단
for i in range(1,n+1):
for j in range(1,n+1):
#한칸씩 +1해서 dp 에 저장
dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+graph[i-1][j-1]이런식으로 하여 누적합을 표현하는 dp 그래프를 만들어 준 후
답은
ans = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]
해당 점화식을 통해 구해주면 된다.
단순이 두 지점의 누적합을 빼주는 것이 아니라 빼줄 부분을 빼주고 중복으로 빼준 것은 다시 더해주고 하는 것을 생각하는 부분이 어려웠던 문제인 것같다.
앞으로는 이런 점화식을 좀 더 스스로 머리를 써서 세워야 할 것 같다.
n,m = map(int,input().split())
graph = []
for i in range(n):
graph.append(list(map(int,input().split())))
dp = [[0]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
for j in range(1,n+1):
#한칸씩 +1해서 dp 에 저장
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())
ans = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]
print(ans)
