알고리즘 문제 풀이 50번 : 영지(territory)선택:(small)

 

목차

---

• 문항 분석

• Code

• 결과 및 분석

---

문항 분석

 

전체 땅에서 주어지는 최대의 오렌지나무가 포함되는 지역 선택하기.

문제 진행 : 먼저 입력 받은 크기의 2차원 배열을 할당 받고, 각 공간에 값을 할당 받는다.
for문을 돌며 각 공간으로부터 할당받을 수 있는 영지의 크기를 바탕으로 순회하며, 최대 개수인 곳이 좌표를 저장하고, 최대 개수를 저장한다.

최대 개수를 출력.(좌표는 필요 없음.)

Code

//
//  50_territory(small).cpp
//  Algorithm
//
//  Created by WANKI KIM on 2021/01/13.
//

#include <iostream>
using namespace std;

struct point{
    int x;
    int y;
};
int main()
{
    int h,w;
    cin >> h >>w;
    
    int **mat = new int*[h];
    for(int i=0;i<h;i++){
        mat[i] = new int[w];
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++)
        {
            cin >> mat[i][j];
        }
    }
    
    int miniH, miniW;
    cin >> miniH >> miniW;
    int sum;
    int result=INT_MIN;
    point point;
    point.x=0; point.y=0;
    for(int i=0;i<h-miniH+1;i++){
        for(int j=0;j<w-miniH+1;j++){
            sum = 0;
            for(int y=0;y<miniH;y++){
                for(int x=0;x<miniW;x++){
                    sum +=mat[i+y][j+x];
                }
            }
            if(sum>result){
                result = sum;
                point.x = j;
                point.y = i;
            }
        }
    }
    
    cout << result << endl;
    cout << point.x << " " << point.y << endl;
    
    
    return 0;
}

결과 및 분석

 

for loop를 총 4번이나 중첩해서 사용했다.

위와 같이 for 반복문을 많이 사용할 경우, 실행시간이 기하급수적으로 늘어나는 문제가 발생할 수 있으므로, 다음 문항에서 해당 문제를 해결해보려한다.

 

 

해당 글은 'it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코테 대비' 강의를 수강하며, 개인적으로 정리하기 위해 업로드하였습니다.

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