[알고리즘 연습] 영지 선택 (DP 맛보기)

영지 선택

• 세로 H, 가로 W의 영지가 있다. 영지의 각 좌표에는 해당 좌표의 오렌지나무 개수정보가 주어진다.
• 황제가 나에게 이 중 세로 HH, 가로 WW의 영지를 준다고 한다. 그런데 나는 최대한 많은 오렌지나무를 가지고 싶다.
• 가능한 모든 경우를 찾아 가장 많은 오렌지나무를 얻었을 때의 개수를 출력하시오.

---

풀이

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int h, w, hh, ww, i, j, tmp, max=0;

    cin >> h >> w;
    vector< vector<int> > oranges(h+1, vector<int>(w+1));
    vector< vector<int> > doranges(h+1, vector<int>(w+1));

    for(i=1; i<=h; i++) {
        for(j=1; j<=w; j++) {
            cin >> oranges[i][j];
            doranges[i][j] = doranges[i-1][j] + doranges[i][j-1] - doranges[i-1][j-1] + oranges[i][j] ;
        }        
    }

    cin >> hh >> ww;

    for(i=hh; i<=h; i++) {
        for(j=ww; j<=w; j++) {
            tmp = doranges[i][j] - doranges[i-hh][j] - doranges[i][j-ww] + doranges[i-hh][j-ww];
            if (tmp > max) {
                max = tmp;
            }
        }    
    }

    cout << max;

    return 0;
}

• 이중 for문안에 이중 for문을 넣어 일일히 모든 sum을 구하는 방법도 있지만, 이는 효율적인 방법이 아니다.
• 따라서 간단한 DP을 진행한다. 사실 DP라고 하기도 애매한 수준이다. (cf. about DP)
• orange의 개수를 저장하는 oranges와 더불어, 각 영지의 누적 오렌지나무 개수 합을 저장하는 doranges를 함께 만드는 것이다.
• 이 때, 두 vector 모두 w+1와 h+1의 크기로 만들고 반복문 돌면서 값을 저장할 때는 (1,1)부터 받도록 하는 것이 포인트이다.
• 사실 그냥 w,h로 vector를 생성하고 (0,0) 상관은 없지만 doranges를 구성하고 이후 이를 활용할때 많은 if else문이 필요해진다. (i혹은 j가 0보다 작아질 경우를 대비하여 예외를 체크해야하기 때문이다.)
• doranges는 (1,1)부터 각 좌표까지 누적된 오렌지나무의 개수를 갖는다. 이는 doranges[i-1][j] + doranges[i][j-1] - doranges[i-1][j-1] + oranges[i][j]를 통해 구할 수 있다. 가로 혹은 세로가 0인 부분은 모두 0으로 초기화되어 있기 때문에 따로 예외처리를 해주지 않아도 된다.
• doranges를 활용하면 반복연산없이 바로 해당 케이스의 오렌지나무 개수합을 구할 수 있다. (doranges[i][j] - doranges[i-hh][j] - doranges[i][j-ww] + doranges[i-hh][j-ww])
• 이를 기반으로 단순 최댓값 구하기를 진행하면 답을 도출할 수 있다.