14391 종이조각

https://www.acmicpc.net/problem/14391

14391번: 종이 조각

문제 : n*m직사각형 판을 작은 직사각형 조각으로 자르려고 한다 (이때 직사각형은 1*1칸마다 숫자가 적혀있다)

가로 조각은 왼쪽부터 , 세로 조각은 위에서부터 숫자를 읽어준다.

종이를 적절히 잘라서 조각의 숫자 합의 최대값을 찾아라

 

해결 : 

 (1 ≤ N, M ≤ 4) 

N,M이 작다 ----> 브루트포스로 접근해보자

 어떤 수에 우리가 도달했을 때 (가로 or 세로 ) 중에 고를 수 있다.

따라서, 2^(N*M)의 경우가 발생한다.

 

1) 직사각형으로 자르기 : 가로 (- ,0)   세로 (| ,1)

 

- - - |        0001   

| | - |         1101

| | | |         1111

- - | |         0011

 

 

한 행의 값의 범위는 0 ~ 2^m - 1 

즉 저 범위의 숫자 중에 n개를 (중복되는 수 포함) 골라서

조각의 합을 계산하자.

이 과정을 재귀적으로 구현해보려고 함(다른 방법이 있을 수도?)

 

 

2) 조각의 합을 계산하기

십진수를 이진수로 바꿈. 이진수를 참고하여 숫자를 읽기!

 

 

코드

#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;

int n,m;
int ans;
char sc[5][5];
int bit[5][5];
bool visited[5][5];

string getNum(int r, int c){
    string num ="";
    num = sc[r][c];
    visited[r][c] = true;
    if(bit[r][c]){ // 세로
        for(int i = r+1; i < n; i++){
            if(bit[r][c] == bit[i][c]){
                num += sc[i][c];
                visited[i][c] =true;
            }
            else break;
        }
    }
    else{ //가로
         for(int i = c+1; i < m; i++){
            if(bit[r][c] == bit[r][i]){
                num += sc[r][i];
                visited[r][i] =true;
            }
            else break;
        }
    }
    return num;
}

int getSum(vector<int> num){
    int row = 0, sum = 0;
    memset(visited,false,sizeof(visited));
    memset(bit,0,sizeof(bit));
    
   for(auto x : num){
        int col = m;
        while(x != 0){
            bit[row][--col] = x % 2;
            x /= 2;
        }
        row++;
    }
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(!visited[i][j]) sum += stoi(getNum(i,j));
        }
    } 
    return sum;
}

void solution(vector<int> num){
    if(num.size() == n) {
        ans = max(ans,getSum(num));
        return;
    }
    for(int i = 0; i < pow(2,m); i++){
        num.push_back(i);
        solution(num);
        num.pop_back();
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(0);
    vector<int> v;
    cin>>n>>m;
    
    for(int i=0; i<n; i++){
        string s;cin>>s;
        for(int j=0;j<m;j++){
            sc[i][j] = s[j];
        }
    }
    
    solution(v);
    cout<<ans;
    return 0;
}