백준 14391번 종이 조각 - C++ 풀이

---

 

1. 각 칸을 세로로 사용할지 가로로 사용할지 결정한 뒤, 전체 조각의 합을 구한다.
2. 모든 경우 중 전체 조각의 합이 가장 큰 경우를 고른다.

 

1. 각 칸을 세로로 사용할지 가로로 사용할지 결정한 뒤, 전체 조각의 합을 구한다.

 모든 칸에 대해 각 칸을 세로 조각으로 사용할지, 가로 조각으로 사용할지 결정한다. 결정 결과를 비트 마스킹으로 나타낼 수 있다. (ex. 가로는 1 세로는 0) 모두 결정한 뒤에는 전체 조각의 합을 구하면 된다. 전체 조각의 합을 구할 때, 인접한 두 칸 A, B가 똑같이 가로 또는 세로 칸일 경우, A와 B는 서로 이어져 있는 긴 조각으로 처리해주어야 한다.

 

2. 모든 경우 중 전체 조각의 합이 가장 큰 경우를 고른다.

 모든 경우를 고려한 뒤 그 중 합이 가장 큰 경우를 고른다. 모든 경우를 고려하는 비트 마스크의 범위는 [0, (1 << N*M) - 1]이 되고, N*M이 최대 16이므로 브루트포스를 사용해도 충분하다.

 

반응형

---

#include <iostream>
#include <vector>

using namespace std;

int N, M;
int board[4][4];

bool isHorizontal(int r, int c, int mask) {
    int idx = r*M + c;
    return ((1 << idx) & mask) != 0;
}

int calcSum(int mask) {
    int ret = 0;
    vector<vector<bool>> visit(N, vector<bool>(M, 0));
    
    for (int i=0; i<N*M; i++) {
        int r = i/M;
        int c = i%M;
        int nr = r;
        int nc = c;
        int sum = 0;
        
        while (nr < N && nc < M &&
               !visit[nr][nc] &&
               isHorizontal(r, c, mask) == isHorizontal(nr, nc, mask)) {
            sum *= 10;
            sum += board[nr][nc];
            visit[nr][nc] = true;
            
            if (isHorizontal(r, c, mask)) nc++; // 가로 조각
            else nr++;                          // 세로 조각
        }

        ret += sum;
    }
    
    return ret;
}

int optimize() {
    int ret = 0;
    
    for (int i=0; i<(1<<N*M); i++) {
        ret = max(ret, calcSum(i));    
    }
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    
    for (int i=0; i<N; i++) {
        string temp;
        cin >> temp;
        
        for (int j=0; j<M; j++) {
            board[i][j] = temp[j] - '0';    
        }
    }
    
    cout << optimize();

    return 0;
}