영지(territory) 선택 : (large)

it 취업을위한알고리즘문제풀이

문제

알고리즘 개선 전 소스코드

//50. 영지(territory) 선택 : (small)
#include <stdio.h>
int main() {
    //freopen("input.txt", "rt", stdin);
    int map[51][51];
    int H, W, HH, HW, count = 0, maxCount = 0;

    //입력
    scanf("%d %d", &H, &W);
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            scanf("%d", &map[i][j]);
        }
    }
    scanf("%d %d", &HH, &HW);

    //알고리즘

    //i,j는 누적해서 더해 갈 시작위치 값을 의미
    for (int i = 0; i <= H - HH; ++i) {
        for (int j = 0; j <= W - HW; ++j) {
            count = 0;

            //세로는 몇회, 가로는 몇 회까지만 더 할지
            for (int k = 0; k < HH; ++k) {
                for (int l = 0; l < HW; ++l) {
                    count += map[i + k][j + l];
                }
            }
            //for (int k = i; k <i + HH; ++k) {
             //     for (int l = j; l <j + HW; ++l) {
             //         area += map[k][l];
             //     }
             // }
            if (maxCount < count) {
                maxCount = count;
            }
        }
    }

    printf("%d", maxCount);

    return 0;
}

알고리즘 개선 후 소스코드

//51. 영지(territory) 선택 : (large)
 #include <stdio.h>
 #include <stdlib.h>
 int main() {
     freopen("input.txt", "rt", stdin);
     int** map;
     int H, W, HH, HW, firstCount = 0, curCount = 0, count = 0, maxCount = 0;

     //입력
     scanf("%d %d", &H, &W);

     //2차원 동적 배열 할당
     map = (int**)malloc(sizeof(int*) * H);
     for (int i = 0; i < H; ++i) {
         //map[i] = (int*)malloc(sizeof(int) * W);
         map[i] = (int*)calloc(W,sizeof(int));//동적할당 된 메모리공간을 0으로 초기화 하면서 동적할당
     }


     for (int i = 0; i < H; ++i) {
         for (int j = 0; j < W; ++j) {
             scanf("%d", &map[i][j]);
         }
     }
     scanf("%d %d", &HH, &HW);

 //    //i,j는 구간의 좌측 대각선 꼭지점
     for (int i = 0; i <= H - HH; ++i) {

         int j = 0;
         curCount = 0;
         //행 바뀔때마다 다시 기준 넓이 구하기
         for (int k = i; k < i + HH; ++k) {
             for (int l = j; l < j + HW; ++l) {
                 curCount += map[k][l];
             }
         }
         //firstArea를 두는 이유는 다음 2중for문에서 매번 첫번째 구간의 넓이는 사라지기 때문 미리 저장하고 최대값과 비교해서 최대값을 빼야한다.
         firstCount = curCount;

         for (int j = 0; j < W - HW; ++j) {

             //새롭게 더해질 곳은 기준으로 부터 현수가 갖게될 가로길이 만큼 옆으로 간곳
             //빠져야 할 곳은 가장 좌측(기준점에서 주어진 세로높이까지의 열)모두
             //"행의 기준점+HW"인 더하고 기준값 빼고 기준 값 다음 열에서 같은 행위 반복
             //printf("(%d,%d),cur:%d\n", i, j, curArea);

             for (int k = 0; k < HH; ++k) {
                 //    printf("%d\n", map[i + k][j + HW]);
                 curCount = curCount + (map[i + k][j + HW] - map[i + k][j]);
             }

             // 최대값 구하기
             if (curCount > maxCount)
                 maxCount = curCount;
             if (firstCount > maxCount)
                 maxCount = firstCount;

         }
     }

     printf("%d", maxCount);

     for (int i = 0; i < H; ++i) {
         free(map[i]);
     }
     free(map);
     return 0;
 }