[PCCE 기출문제] 10번 / 공원

문제 위치 : https://school.programmers.co.kr/learn/courses/30/lessons/340198

프로그래머스

 

가능한 깔 수 있는 최대 크기의 돗자리를 구하는 문제이다.

반복적으로 진행하여 최댓값을 구하는 것이 중요한 문제이므로 돗자리 설치 가능 여부를 함수화하여 분리하였다.

 

함수는 완전 탐색으로 진행하였다.

 

이후 모든 돗자리의 한 변 크기에 대하여 반복적으로 함수를 진행하여 최대값을 탐색하였다.

#include <string>
#include <vector>

using namespace std;

bool isSizeok(int mat_size, vector<vector<string>> park){
    bool ok = true;
    int park_row, park_col;
    park_row = park.size();
    park_col = park[0].size();
    
   for(int l = 0; l <= park_row - mat_size; l++) {
        for(int k = 0; k <= park_col - mat_size; k++) {
            ok = true;
            for(int i = 0; i < mat_size; i++) {
                for(int j = 0; j < mat_size; j++) {
                    if (park[i + l][j + k] != "-1") {
                        ok = false;
                        break;
                    }
                }
                if (!ok) {
                    break;
                }
            }
            if (ok) {
                return true;
            }
        }
    }
    return false; // 조건을 만족하는 매트릭스가 없으면 false 리턴
}

int solution(vector<int> mats, vector<vector<string>> park) {
    int answer = 0;
    for(int i : mats){
        if(isSizeok(i, park)){
            if(i > answer) answer = i;
        }
    }
    if(answer == 0) answer--;
    return answer;
}