[BOJ][DP] 2167. 2차원 배열의 합

문제 -> https://www.acmicpc.net/problem/2167

그림을 그려서 생각을하면 간단히 풀리는 문제. 

(애초에 문제는 거의 다 그림으로 풀지만..)

이 문제의 설명이 오해의 소지가 있다..

[i][j] 부터 [x][y]까지의 합이라는 의미는 아래의 의미다.

처음에 잘 못 이해하는바람에 왜 틀리는지 이해가 안갔었다.

그냥 무작정 (i, j) ~ (x, y)의 합을 구해도 정답이 뜬다고는 하는데,

시간복잡도가 점점 커질 수 밖에 없다. 

그래서 효율적으로 각 dp배열에 (1,1)부터 자신까지의 합을 구해놓는다.

그러믄, 합을 구하는 점화식을 생각해보자.

빨간색 체크표시가 된 위치를 dp[x][y]라 치자. 

각각 다른색으로 칠해진 사각형은 이미 구해진 dp 값이다.

일단 더하자.

dp[x][y] = dp[x][y-1] + dp[x-1][y] + dp[x][y]

(참고로 나는 그냥 dp에 배열의 값을 넣어줬다. 결과에 상관이 지장이 없기 때문.)

근데 문제가 있다.

겹치는 부분이 발생한다.

그래서 그 겹치는 부분을 빼줘야겠지?

그렇게 되면 위의 점화식에 - dp[x-1][y-1]만 추가해주면 끝이다.

dp[x][y] = dp[x][y-1] + dp[x-1][y] + dp[x][y] - dp[x-1][y-1].

소스(Github)