[BOJ] 14391 종이조각 C++

 

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

14391번: 종이 조각

처음에는 무작정 가로로 가장 길게 나누고 세로로 가장 길게 나눈 것 중에서 가장 큰 값이 무조건 답일 줄 알았는데 아니었다..

 

반례를 보니

1 0 0 0

0 0 0 1

0 0 0 0

1 0 0 0

인 경우가 있을 때, 내 방법은 2001을 출력하지만 답은 2010이다. 결국 모든 경우의 수를 고려해야 한다는 것이다. 다른 사람의 코드를 참조하여 비트마스킹으로 구현하였다. 아직 비트마스킹을 활용하기엔 많이 부족한 것 같다...

어떻게 이 문제를 비트마스킹으로 풀 수 있을까? 일단 최대 N과 M이 4이므로 해당 칸이 가로에 속할 것인지 세로에 속할 것인지의 경우의 수는 2^16이므로 이진법으로 모든 경우를 표현 할 수 있다.

위와 같은 경우 일 경우 가로에 속한 경우를 1, 세로에 속할 경우를 0이라 한다면 아래와 같이 표현 된다.

그럼 해당 경우는 이진수 1110 0010 0000 1100 인 경우라고 할 수 있다. 이를 활용하여 코드를 짜면 된다.

 

코드

#include <iostream>
#include <cmath>
using namespace std;
int info[4][4];
int row[4],col[4];
int N,M;
int main(){
    cin>>N>>M;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            int a;
            scanf("%1d",&a);
            info[i][j]=a;
        }
    }
    int ans=0;
    for(int k=0;k<(1<<N*M);k++){
        int total=0;
        //가로 1
        for(int i=0;i<N;i++){
            int r_sum=0;
            for(int j=0;j<M;j++){
                int x=i*M+j; // i*M+j는 이진수에서 몇 번째인지를 의미한다.
                if(!((k&(1<<x)))){
                    r_sum=(r_sum*10+info[i][j]);
                }else{
                    total+=r_sum;
                    r_sum=0;
                }
            }
            total+=r_sum;
        }
        //세로 0
        for(int j=0;j<M;j++){
            int c_sum=0;
            for(int i=0;i<N;i++){
                int x=i*M+j;
                if(k&(1<<x)){
                    c_sum=(c_sum*10+info[i][j]);
                }else{
                    total+=c_sum;
                    c_sum=0;
                }
            }
            total+=c_sum;
        }
        ans=max(total,ans);
    }
    cout<<ans;
    return 0;
}