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

돗자리를 둘 자리가 0일 수도 있다. 완전 탐색으로토 풀이할 수 있지만 for문이 5개 정도 만들어져서 시간 초과가 날 거 같아서 포기했다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int solution(vector<int> mats, vector<vector<string>> park) {
    int answer = -1;
    int i, j;
    vector<vector<int>> DP(park.size(), vector<int>(park[0].size(), 0));
    int max_count = 0;

    //mats : 지민이가 가진 돗자리 종류
    for(i = 0; i < park.size(); i++){
        for(j = 0; j < park[i].size(); j++){
            if(park[i][j] == "-1"){
                if(i == 0 || j == 0){
                    DP[i][j] = 1;
                }
                else{
                    DP[i][j] = min({DP[i - 1][j], DP[i][j - 1], DP[i - 1][j - 1]}) + 1;
                }
                max_count = max(max_count, DP[i][j]);
            }
            else{
                DP[i][j] = 0;
            }
        }
    }
    
    for(i = 0; i < DP.size(); i++){
        for(j = 0; j < DP[i].size(); j++){
            cout << DP[i][j] << " ";
        }
        cout << "\n";
    }
    
    sort(mats.begin(), mats.end(), greater<>());
    for(i = 0; i < mats.size(); i++){
        if(mats[i] <= max_count){
            answer = mats[i];
            break;
        }
    }
    
    return answer;
}