50. 영지(DP)

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅

 

 

입력예제 1

6 7

3 5 1 3 1 3 2

1 2 1 3 1 1 2

1 3 1 5 1 3 4

5 1 1 3 1 3 2

3 1 1 3 1 1 2

1 3 1 3 1 2 2

2 3 

 

출력예제 1

16

 

풀이 

- 2x3배열 땅의 나무 카운팅 시 가장 많은 땅을 찾는다(4중 for문으로 찾을 수도 있지만 timeout 당할 수 있음, 비효율적)

- dy 배열로 누적합계를 만든다. dy[i][j] = 왼쪽+위쪽 -왼쪽&위쪽+원배열[i][j] 

- dy배열을 완성한 후 찾을 땅의 n, m를 입력받음

- dy배열에서 합계가 가장 큰 땅을 찾기 위해 가로로 -n만큼 세로로 -m만큼 떨어진 곳의 값을 뺀 후 -n, -m인 곳의 값을 더해준다

(중복으로 빼지는 부분 다시 더해줌)

- 2*3크기의 땅이기 때문에 (2,3)좌표 부터 2x3 땅의 합계를 구하면 된다.

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int a[701][701], dy[701][701];

// 51. 영지선택 Large(DP)
int main() {
    int h, w, n, m, i, j, tmp, max=-2147000000;
    scanf("%d %d", &h, &w); //전체 땅
    for(i=1;i<=h;i++){
        for(j=1;j<=w;j++){
            scanf("%d", &a[i][j]);
            dy[i][j]=dy[i-1][j]+dy[i][j-1]-dy[i-1][j-1]+a[i][j];
            //해당 좌표의 왼, 위,왼쪽에서 위쪽을 뺀 후 해당 좌표값을 더해서 dy를 만듬
        }
    }
    scanf("%d %d", &n, &m); //받을 땅
    for(i=n;i<=h;i++){
        for(j=m;j<=w;j++){
            tmp=dy[i][j]-dy[i-n][j]-dy[i][j-m]+dy[i-n][j-m];
            if(tmp>max) max=tmp;
        }
    }
    printf("%d\n", max);
    return 0;
}