[백준/Python] - 11660 구간 합 구하기 5

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

 

제출코드

import sys

input = sys.stdin.readline

N , M = map(int,input().split())

N_list = []

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

for _ in range(N):

    N_list.append(list(map(int,input().split())))

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] + N_list[i-1][j-1] # i = 1 j = 2 N_list[0][2] => 2

for _ 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)

문제 접근은

구간별로의 합을 전부 구한 뒤 나머지의 구간들을 빼서 답을 구한다라고 접근은 맞게 했는데

이걸 DP를 사용해서 구해야하는지 몰랐다....

나머지 구간들을 어떻게 빼야하고 구간 합을 어떻게 다 더해야 하는지도 몰라서 접근만 맞게했다...

 

일단 1부터 시작하기 위해 dp를 확장해서 0인 행과 0인 열을 0으로 초기화한다.

해당 테이블에서 보자

우리가 원하는 값은 8이라고 했을 때

이전 행에서의 누적 합 이전 열에서의 누적합을 더한다.

그런데 여기서

이전 행 : 3 = 2 + 1

이전 열 : 3 = 2 + 1 이 된다.

그럼 1을 두번 더하는 것이므로 누적합에 1을 빼줘야된다는 것이다.

그래서 

이전 행 + 이전 열 - 이전 행과 열 + 해당 N_list의 원소값을 더해주면 해당 2,2까지의 누적합은 8이 되는 것이다.

 

그리고 구간 합을 구할때는 반대로 생각하면 된다.

끝 구간 까지의 합을 구하고, x1과 y1이전 까지의 누적합을 빼주면 된다.

[x1-1][y2] ==> x1 이전 행 까지의 누적 합

[x2][y1-1] ==> y1 이전 행 까지의 누적 합

그런데 여기서도 겹치는 부분이 생긴다. 그건 [x1-1][y1-1]부분이므로 이 값을 더해줘야지 구간 합이 성립이 된다.

---

정말 백준문제를 풀면서 계속 느끼는건데 문제 만든사람도 천재고 

문제를 푸는사람도 대단하다고 느낀다...