군대에서_코딩하기_알고리즘_19

오늘 문제는 생각보다 괜찮은 문제여서 나중에 두고두고 봐야겠다는 생각에 업로드를 한다.
우선 문제가 조금 기니까 캡쳐로 남기겠다.

우선 영지를 저장할 2차원 배열을 벡터로 선언해주고, 또다른 2차원 배열을 벡터로 선언해줘서, DP 배열을 만든다. 이유는, 하나의 2차원 배열에서 하나하나 다 노가다로 영역을 구하면 분명 time_limit이 뜰것이기 때문에..
DP배열을 만들때, 처음에 영지를 만들기 위해 입력했던 배열을 이용하여 만드는데, 참..말로 설명하기는 조금 어렵지만 문제를 잘 읽어보고 아래 그림을 보면 이해가 갈것이다..
밑에 그림의 4행 4열의 18이라는 숫자를 도출하기 위해서는 빨간색 부분과 파란색 부분을 한번씩 빼주고, 3행 3열의 숫자를 한번 더해주고, 원래 영지의 4행 4열을 한번 더해주면 18이 도출된다.
당연히 이해가 안가겠지만 아무튼 나는 이해됨..
애초에 DP라는 게 하나의 문제를 쪼개서 접근하는것이기 때문에, 사람마다 다를수도 있다..
코드는 다음과 같다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
    
    int H, W, h, w, i, j, max=0, temp;
    
    cin>>H>>W;
    
    vector<vector<int> > map(H+2, vector<int>(W+2));
    
    vector<vector<int> > dp(H+2, vector<int>(W+2));
  //요런 형식으로 vector 2차원 배열을 선언해주면 공간도 아낄 수 있고 매우 좋다!  
    
    for(i=1; i<=H; i++){
        for(j=1; j<=W; j++){
            cin>>map[i][j];
        }
    }
    
    for(i=1; i<=H; i++){
        for(j=1; j<=W; j++){
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + map[i][j];
        }
    }
    //DP 배열을 만들어주는 부분인데, 위에서 말한 빨간색 부분과 파란색 부분을 한번씩 빼주고, 
    //겹친 부분을 다시 더해준 다음에 map(원래 영지) 부분의 인덱스를 더해준다
    
    cin>>h>>w;
    
    for(i=h; i<=H; i++){
        for(j=w; j<=W; j++){
            temp = dp[i][j] - dp[i-h][j] - dp[i][j-w] + dp[i-h][j-w];
            if(temp>max){
                max = temp;
            }
        }
    }
    //이 부분도 이제 기가 막힌 부분인데.. DP배열을 다 만들고나서 정해진 h행과 w열 만큼의
    //최댓값을 구하는 절차이다. 이것도 아까 DP배열을 만들때와 비슷하게 겹치는 부분을 빼주고
    //두번 빼준 부분은 다시 겹치는 부분만큼 더해준다!
    
    /*for(i=1; i<=H; i++){
        for(j=1; j<=W; j++){
            cout<<dp[i][j]<<" ";
            
        }    
        cout<<endl;
    } */
    
    cout<<max;
}