백준 14391 / 종이 조각

문제를 풀 방법을 궁리하는데 꽤 걸렸다.

내가 발견한 해결책은

예를 들어 2x2라면 0000,0001,0010........1111(총 16가지)를 배열에 넣고 (넣는 방법은 이진수를 이용했다)

0이면 가로 1이면 세로로 정한다음

가로로 한번 읽어 생긴 값과 세로로 한번 읽어 생긴 값을 더하는 것이다.

어려운 문제처럼 보이지만 해결법만 찾으면 그리 어렵지 않게 풀 수 있는 문제다.

코드

#include<iostream>
#include<stdio.h>
#include<queue>
#include<vector>
#include<math.h>
#include<memory.h>
using namespace std;
 
int map[4][4];
int dir[4][4];
bool check[4][4];
 
vector<int>arr;
 
int n, m;
 
vector<int>change2jin(int i) {
 
    vector<int>tmp;
 
    tmp.resize(n*m);
 
    for (int j = 0; j < n*m; j++) {
        tmp[j] = i % 2;
        i = i / 2;
    }
    return tmp;
}
 
int main() {
 
    //freopen("Text.txt", "r", stdin);
 
    cin >> n >> m;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%1d", &map[i][j]);
        }
    }
    
    arr.resize(n*m);
 
    int ans = -1;
 
    for (int i = 0; i < pow(2, (n*m)); i++) {
 
        memset(check, false, sizeof(check));
 
        arr = change2jin(i);
 
        int nl = 0;
        int ml = 0;
 
        for (int j = 0; j < n*m; j++) {
            if (ml == m) {
                nl++;
                ml = 0;
            }
            dir[nl][ml] = arr[j];
            ml++;
        }
 
        int cnt = 0;
 
        for (int i = 0; i < n; i++) {
        
            int ten = 1;
            for (int j = m-1; j >=0; j--) {
                if (dir[i][j] == 0 && check[i][j]==false) {
                    check[i][j] = true;
                    cnt += map[i][j] *ten;
                    ten = ten * 10;
                }
                if (dir[i][j] == 1)ten = 1;
            }
        }
 
        for (int j = 0; j < m; j++) {
            int ten = 1;
            for (int i = n - 1; i >= 0; i--) {
                if (dir[i][j] == 1 && check[i][j] == false) {
                    check[i][j] = true;
                    cnt += map[i][j] * ten;
                    ten = ten * 10;
                }
                if (dir[i][j] == 0)ten = 1;
 
            }
        }
 
        if (ans < cnt) {
            ans = cnt;
        }    
    }
    cout << ans;
}