[백준][DP] 2167번 2차원 배열의 합

문제

각 배열의 원소가 주어지고, i, j, x, y가 주어질 때 (i, j)칸에서 (x, y)칸까지의 합을 구하시오.

문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/2167)

풀이

처음에는 단순히 일렬로 놓여있는 배열이라 생각하고 (i, j)칸에서부터 (x, y)칸까지의 합을 구하는 줄 알았는데 그게 아니라 사각형을 그린다고 했을 때 왼쪽 위의 점이 (i, j)이고 오른쪽 아래점이 (x, y)인 것이었습니다. 어떻게하면 숫자가 크지 않다면 2중 for문을 통해서 구할 수도 있겠지만 합을 구해야하는 경우의 수가 최대 10000개가 될 수 있기 때문에 dp를 이용해야했습니다. 처음엔 전.혀 감이오지 않아서 넘겨버렸던 문제였는데 그림을 그려서 생각해보니 쉽게 생각할 수 있었습니다! 임의의 i, j에 대해서 dp[i][j]는 (1, 1)에서 (i, j)까지의 합으로 만들어주었습니다. 그렇지만 이 값을 통해서 바로 (i, j)칸에서부터 (x, y)칸까지의 합=dp[x][y]-dp[i-1][j-1] 는 성립하지 않습니다. dp[x][y]에서 dp[i-1][j-1]를빼주더라도 우리가 구하고자 하는 사각형의 왼쪽과 아래쪽에 불필요한 값을 다 포함하고 있다는 것을 알 수 있습니다. 왼쪽 사각형의 값을 빼주기 위해 dp[x][j-1]을 사용하고 아래쪽의 사각형 값을 빼주기 위해 dp[i-1][y]를 사용합니다. 하지만 이 두값을 사용하면 dp[i-1][j-1]의 값이 2번이나 뺄셈되는 것을 알 수 있습니다. 즉 result= dp[x][y]-dp[x][j-1]-dp[i-1][y]+dp[i-1][j-1]을 해주면 결과값을 만들어낼 수 있습니다. 손으로 그려보지 않고 머리로 생각하려고 해서 푸는데 오래 걸린 문제입니다.(ㅠㅠ) 그리고 처음에는 index를 0부터 사용해서 입력받은 후 i-1, j-1, x-1,y-1와 같이 사용해줬는데 예외처리를 해줘야해서 그 처리보다 1부터 시작점을 잡아주도록 바꾸는게 더 빠르게 해결할 수 있었습니다.

코드

https://github.com/kswim/Algorithm/blob/master/DP/2167.cpp