백준 2차원 배열의 합 2167번 해설(JAVA)

문제

입력

 

출력

 

해설:

우리는 해당 배열을 입력 받았다.

 

그리고 아래 입력받은 좌표값에 따라서 (i,j)~(x,y)까지의 합을  입력받은 배열을 기준으로 구해야한다.

i j x y

1 1 2 3

1 2 1 2

1 3 2 3

 

출력값은 총 3가지

1. (1,1)~(2,3) 까지의 합 =63

2. (1,2)~(1,2) 까지의 합 =2

3. (1,3)~(2,3) 까지의 합 =36

1번과 2번은 쉽게 이해할수있다. 1번은 그대로 누적합을 계산하면 나오는것이고 2번 또한 마찬가지이다.

그러나 3번을 볼때 고민하게 된다, 어떻게 나오는 것일까? 

(1,3) 부터 시작해서 누적합으로 구했을때 360라는 값은 나오지 않는다. 누적합계를 위한 배열을 따로 생성해서 공식을 찾아보자!

위의 공식을 통해 나온 점화식은 예를 들어서 (x,y) 까지의 누적합을 알고싶다면?

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

이라는 점화식이 나오게 된다.

빨간색 부분은 공통적으로 dp[x][y] 을 구할때 위의 값과 왼쪽값을 더하게 되는데 중복으로 발생하는 숫자를 한번 빼줘야한다.

이제 누적합의 dp 배열이 완성됬다.

그러면 이제 (1,3)~(2,3) 까지의 합 =36 이 나오게 할려면

dp[x][y]-dp[i-1][y]-dp[x][j-1]+dp[i-1][j-1] 점화식이 나오는데 해당 설명은 필자로 해당 사이트를 보고 이해했음

https://wedul.site/420