[백준 #14391] 종이조각

개요

---

완탐으로 풀었다.

크기가 N, M <=4라서 할만하다.

이것 역시 boardcover처럼 중복으로 자르면 +1, 자른거 취소하면 -1 해줬다.

 

 

코드(정답, 1988KB, 8ms)

---

/**
 * @name: 종이조각
 * @link: https://www.acmicpc.net/problem/14391
 * @date 2020-05-05
 * @author sunmon
 * TIP: 
**/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
vector<string> paper;
vector<vector<int> > cutted;    //cutted[i][j] : 종이가 잘린 횟수

const int direction[2][2] = {{0,1},{1,0}};  //가로, 세로

bool cutting(int i, int j, int len, int dir, int flag){
    bool ok = true;
    int di = direction[dir][0], dj = direction[dir][1];
    for(int k = 0; k < len; k++){
        if((cutted[i][j] += flag) > 1) ok = false;
        i += di; j += dj;
    }
    return ok;
}

int getVal(int i, int j, int len, int dir){
    string str;
    if(dir ==0) str = paper[i].substr(j, len);  //가로
    else{   //세로
        for(int k  = 0; k<len; k++)
            str += string(1,paper[i+k][j]);
    }
    return stoi(str);
}

int solve(int n, int m){
    //아직 안 자른 i,j 찾기
    int i = -1, j = -1;
    for(int k = 0; k<n; k++){
        for(int l = 0; l<m; l++){
            if(cutted[k][l]<1){
                i = k, j = l;
                break;
            }
        }
        if(i != -1) break;
    }
    //다 잘랐으면 탐색 종료
    if(i == -1) return 0;
    
    int ret = 0;
    int maxLen[2] = {m-j, n-i};
    for(int dir = 0; dir < 2; ++dir){
        for(int len = 1+dir; len <= maxLen[dir]; ++len){
            if(cutting(i,j,len,dir,1)) 
                ret = max(ret, getVal(i,j,len,dir)+solve(n,m));
            cutting(i,j,len,dir,-1);
        }    
    }
    return ret;
}
int main(){
    int n, m;
    cin >> n >> m;
    cutted = vector<vector<int> >(n,vector<int>(m));
    for(int i = 0; i<n; i++){
        string str;
        cin >> str;
        paper.push_back(str);

    }
    cout << solve(n,m);
}