[Inflearn] 영지(territory) 선택(large) - DP

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. 이전 문제와 같지만 N의 크기가 다르다.

     기존에 최대 N이 50이라서, 50^4 이 나올 경우 6,250,000 은 1초 안에 연산이 가능하다.

     하지만 이번에는 최대 N이 700이라서, 700^4 이 나올 경우 240,100,000,000...

     그렇기때문에 이전 문제처럼 브루트포스 방법으로는 시간초과가 날 것이다..

     

     반복되는 연산을 최대한 줄여보자.

     H=6, W=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

     sH=2, sW=3

     

    이번에는 sW 만큼의 합을 미리 구해놓는 것이다.

    적어도 이중 반복문이라면 490,000 은 1초 안에 연산이 가능하다.

    각 행을 sW개씩 묶어서 합을 구해놓는다.

     0 0 9 9 5 7 6

     0 0 4 6 5 5 4

     0 0 5 9 7 9 8

     0 0 7 5 5 7 6

     0 0 5 5 5 5 4

     0 0 5 7 5 6 5

     여기서 9 + 4 = 13 은 3+5+1+1+2+1 = 31 의 값과 같다.

     결국 저 굵은 글씨의 숫자들을 sH만큼 더한 합들 중 가장 큰 값을 고르면 되는 것이다!

  2. 1번 방법이 틀린 것은 아니지만..

     강사님의 해결방법이 더 효율적인것 같다. dp를 제대로 사용한 방법이라고 해야할까..

     나는 이중 for문을 돌면서 입력을 다 받은 후 다시 이중 for문을 돌면서 구간합을 구해야 할 것이고,

     다시 이중 for문을 돌면서 각 범위의 합을 구할 것이다. 결국 3N^2 이 되어버리는 것이다..

     하지만, 강사님은 입력을 받으면서 dp에 구간합을 저장하고, 

     탐색하면서 최대 합을 찾기 때문에 2N^2 만에 해답을 찾을 수 있다. 

     H=6, W=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

     sH=2, sW=3

     03 08 09 12 13 16 18

     04 11 13 19 21 25 29

     05 15 18 29 32 39 47

     10 21 25 39 43 53 63

     ...

     여기서 이 과정을 설명하는데에는 너무나 한정적이기에..  

#. Code

#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int W, H, sW, sH;
int dp[701][701];
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int  i, j, tmp, sum, rst = -2147000000;
 
    scanf("%d %d", &H, &W);
 
    for (i = 1; i <= H; i++)
    {
        for (j = 1; j <= W; j++)
        {
            scanf("%d", &tmp);
 
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + tmp;
        }
    }
 
    scanf("%d %d", &sH, &sW);
 
    for (i = sH; i <= H; i++)
    {
        for (j = sW; j <= W; j++)
        {
            sum = dp[i][j] - dp[i - sH][j] - dp[i][j - sW] + dp[i - sH][j - sW];
 
            if (sum > rst)
                rst = sum;
        }
    }
 
    printf("%d\n", rst);
 
    return 0;
}

line 18~26) 에서 입력과 동시에 dp를 채워준다.

line 24는 해당 좌표까지의 영역 안에 있는 오렌지 나무의 개수를 구하기 위한 식이다.

line 34는 다스릴 수 있는 땅의 크기 안에 있는 오렌지 나무의 개수의 합을 구하는 식이다.

전체적인 과정은 영상을 다시 참고하는게 좋을 것 같다.

#. Other code

#include<stdio.h>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int a[701][701], dy[701][701];
 
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];
        }
    }
 
    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;
}

강사님의 해결방법대로 풀었기에 코드가 유사하다.

나중에 다시 풀어봐야지..

DP의 기본(?)적인 방법을 이제 잘 이해해버렸다!

잘 응용할 수 있도록 기초를 잘 박아놔야지!

#. Result

  - Input --------------------------------------------------------

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

------------------------------------------------------------------

  - Output --------------------------------------------------------

16

------------------------------------------------------------------