#15724 주지수(C++)

문제 링크 : www.acmicpc.net/problem/15724

15724번: 주지수

당연하지만 이 문제를 무턱대고 Brutce Force로 풀다가는 시간초과가 날것이다.

 

문제 풀이는 다음과 같다.

 

1. 배열의 값은 1,1부터 n,n까지 주어진다고 가정하자. 따라서 0,0라인은 모두 0이 입력된다.

2	3	4
5	6	7
8	9	10

예시로 arr[4][4]는 위와 같다. (맨 첫번째는 arr[1][1]이며 오른쪽 하단의 값은 arr[3][3]이다.)

 

2. 배열의 1,1부터 i,j까지 누적된 값의 표는 아래와 같다. 

 

2	5	9
7	16	27
15	33	54

dp[4][4]의 배열 값은 위와 같다. 이때 dp[i][j]의 값을 구하는 공식은 아래와 같다.

 

dp[i][j] =arr[i][j]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]

 

예를들어 노랑색 칸에 해당되는 dp[2][2]를 구하려면 

해당값의 왼쪽(파랑)인 dp[2][1], 해당 값의 위쪽(파랑)인 dp[1][2], 해당값의 원본 배열인 arr[2][2], 

이 세가지를 모두 더한뒤 dp[1][1]을 빼주면 된다. 

dp[1][1]을 빼는 이유는 중복으로 더해진 누적값을 제거하기 위함이다. 

 

3. 이제 원하는 크기 만큼 누적된 합을 구해보자. 

2	5	9
7	16	27
15	33	54

만약 위의 테이블에서 파랑색으로 표시된 곳 만큼의 영토를 구한다고 가정해보자. 

dp[3][3]의 값에서 빨간색으로 표시된 arr배열들을 빼주면된다. 

arr배열을 불러오지 않아도 dp만으로도 값을 구할수 있다. 

dp[3][3]에서 dp[1][3]을 빼주고, dp[3][1]을 빼준다. 여기에 중복으로 누적되어 제거된 값을 다시 더하기 위해 dp[1][1]을 더해준다. 

이를 식으로 표현하면 다음과 같다. 

 

arr[a][b]에서 arr[c][d]까지의 합 = dp[c][d]-dp[a-1][d]-dp[c][b-1]+dp[a-1][b-1]

 

이해가 되지 않을 경우 설명을 직접 한번만 그려보는 것을 권장한다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int n=0,m=0,cnt=0,a=0,b=0,c=0,d=0,ans=0,arr[1025][1025] = {0,}, dp[1025][1025] = {0,};

int main(void) {
   ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
   cin >> n >> m;
   for(int i=1; i<=n; i++){
      for(int j=1; j<=m; j++){
         cin >> arr[i][j];
         dp[i][j] = arr[i][j]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]; //마지막은 중복요소 제거
      }
   }
   cin >> m;
   while(m>0){
      cin >> a >> b >> c >> d;
      ans = dp[c][d]-dp[a-1][d]-dp[c][b-1]+dp[a-1][b-1];
      cout << ans << "\n";
      m--;
   }
   return 0;
}