[Inflearn] 영지(territory) 선택(small) : 브루트포스

#. 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. 입력이

     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

     이렇게 주어졌을 때, 6 x 7 크기의 땅에서 2 x 3 크기의 땅을 선택하는데

     얻을 수 있는 오렌지 나무의 최대 개수를 구해야 한다.

    

     최대 땅의 크기가 50 x 50 = 2500 이니까 모든 경우의 수를 탐색해보아도 무관할 것 같다.

     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

     쉽게 생각하면 위 파랑색 구역만 탐색하면서 주변 2x3 구간에 있는 오렌지 나무의 개수를 세주면 된다.

     현재 H=6, W=7 이므로

     H-sH, W-sW 까지만 탐색을 하고

     그 안에서 sH, sW 크기만큼 sum 을 해준 후,가장 큰 sum 값을 rst 에 저장해주면 되겠다!

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

#include <cstdio> #include <vector> #include <algorithm>   using namespace std;   int W, H, sW, sH; int map[51][51];   int main(void) {     freopen("input.txt", "rt", stdin);       int  i, j, k, h, sum, rst = -21470000;       scanf("%d %d", &W, &H);     for (i = 1; i <= W; i++)     {         for (j = 1; j <= H; j++)             scanf("%d", &map[i][j]);     }     scanf("%d %d", &sW, &sH);       for (i = 1; i <= W - sW + 1; i++)     {         for (j = 1; j <= H - sH + 1; j++)         {             sum = 0;               for (k = i; k < i + sW; k++)             {                 for (h = j; h < j + sH; h++)                 {                     sum += map[k][h];                 }             }               if (sum > rst)                 rst = sum;         }     }       printf("%d\n", rst);       return 0; } Colored by Color Scripter

cs

하다보니 사중 반복문이...

완전 비효율적으로 보인다 ㅠ.ㅠ

#. Other code

#include<stdio.h>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int a[51][51];
 
int main(){
    int h, w, n, m, i, j, k, s, sum=0, max=-2147000000;
 
    scanf("%d %d", &h, &w);
    for(i=1; i<=h; i++){
        for(j=1; j<=w; j++){
            scanf("%d", &a[i][j]);
        }
    }
 
    scanf("%d %d", &n, &m);
    for(i=1; i<=h-n+1; i++){
        for(j=1; j<=w-m+1; j++){
            sum=0;
            for(k=i; k<i+n; k++){
                for(s=j; s<j+m; s++){
                    sum=sum+a[k][s];
                }
            }
            if(sum>max){
                max=sum;
            }
        }
    }
 
    printf("%d\n", max);
    return 0;
}

브루트포스로 푸는 문제였다보니 같은 방법으로 사중 반복문이 사용되었다.

#. 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

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