[C/C++] 백준 11660 구간 합 구하기 5 (이차원 구간 합)

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

11660번: 구간 합 구하기 5

구간 합 구하기 문제

 

풀이 방법?

 가장 먼저 드는 생각은 합을 구해야하는 횟수마다 저장되어 있는 2차원 배열에서 이중 for문을 통해 구간 합을 각각 구하는 방법인데 이 방법으로 할 경우 최악의 경우에는 100,000*1024*1024 의 경우를 모두 확인해야하므로 시간 초과가 발생한다.

 

 그렇기 때문에 여기서 제목에 있는 힌트를 빌려 풀이 방법을 생각해보자면 현재 있는 위치까지의 구간합을 저장하여 합을 구해야하는 횟수마다 불러와 최악의 경우에도 경우의 수가 100,000(합을 구해야하는 횟수)+1024*1024(그래프 저장)로 줄일 수 있다. 즉, 반복되는 부분을 미리 저장하여 필요할 때 바로 쓸 수 있는 Dynamic Programming 방법을 이용해야한다!

 

 

점화식?

 Dynamic Programming에서 제일 중요한건 점화식을 찾는 것인데 문제를 잘 읽어보면 (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다는 것을 알 수 있다. 우리는 2차원 배열을 입력받아 

 

v1[j][i]+=v1[j-1][i]+v1[j][i-1]-v1[j-1][i-1]; 

 

라는 식을 통해 (j,i)에서의 구간 합을 저장하면 된다. 즉, 위에 있는 좌표의 부분합(v1[j][i-1])과 왼쪽에 있는 좌표의 부분 합(v1[j-1][i])을 더하면 왼쪽 대각선 위에 있는 좌표의 부분합 부분(v1[j-1][i-1])을 중복이 되므로 그 부분을 제외해주는 것이다,

 

이 방법과 유사하게 (x1, y1)부터 (x2, y2)의 합을 구할 때 구하고자 하는 영역의 계산을 위해서 중복되는 부분을 빼주고 2번 중복되었던 부분을 더해줌으로써 결과값을 알 수 있는데 이것을 이용한 점화식은 아래와 같다.

 

 int result=v1[x2][y2]-(v1[x1-1][y2]+v1[x2][y1-1])+v1[x1-1][y1-1];

 

 

구현!!

구현할 때 꿀팁를 자잘하게 말해보겠다! 

1. 이차원 배열 

이차원 배열을 맨 처음 정의를 할 때 int v1[1025][1025]으로 0으로 초기화하여 정의하고 입력을 받을 때 [0][0]부터 받는 것이 아니라 [1][1]부터 받으면 코드를 훨씬 깔끔하게 만들 수 있다. 이렇게 되면 맨 윗줄과 가장 왼쪽의 있는 줄이 0으로 초기화되어 있기 때문에 점화식을 사용할 때 범위를 넘어가는 조건문을 따로 만들어주지 않아도 되서 더 간단하게 코드를 완성시킬 수 있다. 이차원 DP에서 자주 사용되는 Tip이니 기억하며 좋다!

2. 시간 초과

 시간초과가 뜬 사람은 

 

  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

 

코드를 넣어보면 쉽게 해결 될 수도 있다. 이 것을 넣어야 하는 이유는 아래의 포스팅에 자세히 기술해서 참고하면 된다!!https://donggul-godsang.tistory.com/70 

[C++] 기초부터 공부하기(1. 기초 & 입출력)!

 

 

소스코드!!

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#include<queue>
#include<limits.h>
#include<map>

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역

//int v1[1025][1025];
vector<vector<int>>v1(1025,vector<int>(1025,0));

//vector<pair<int,int>,pair<int,int>> coordinate;

int main() {

  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n,m;
  cin>>n>>m;
  
  for(int j=1;j<=n;j++)
    {
      for(int i=1;i<=n;i++)
        {
          cin>>v1[j][i]; //값 저장
          v1[j][i]+=v1[j-1][i]+v1[j][i-1]-v1[j-1][i-1]; //백터의 현재까지의 합 저장        
        }    
    }
  for(int i=0;i<m;i++)
    {
      int x1,y1,x2,y2;
      cin>>x1>>y1>>x2>>y2;
      int result=v1[x2][y2]-(v1[x1-1][y2]+v1[x2][y1-1])+v1[x1-1][y1-1];
      cout<<result<<"\n";
    }    

}