[BOJ/백준] 14391 종이 조각

● [문제번호 14391] 종이 조각

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

14391번: 종이 조각

 

● 알아야 할 것

: 비트마스크

: 브루트 포스 (Brute Force)

 

● 풀이 과정

: 주어진 문제를 읽고 조각의 최대 총합이라면,

행렬의 가로로만 자른 것과 행렬의 세로로만 자른 것을 비교하면 되는 거 아닌가?
왜 중간에 잘라야하지? 싶어서 구현했더니

채점중의 %가 나오기도 전에 '틀렸습니다.' 가 나왔다.

 

중간에 자를 필요가 있는 반례가 무엇일지 아무리 생각해도 머리아프니 구글링을 했다.

 

: 반례

0 0 0 1

0 0 0 0

0 0 0 0

1 0 0 0

→ 1000 + 100 = 1100

(가로 또는 세로로만 자른다면 1001이 나온다)

 

: 그래서 비트마스크보다 재귀로 하면 안될까 싶었는데

가능은 하지만 행렬의 각 원소가 가로방향 숫자인지 세로방향 숫자인지 조절해야하는 작업이 더 필요했다.

 

비트마스크를 이용하면 방금 언급한 작업을 비트 옮기는 것으로 대체된다.

 

● 주의 할 것

: paper는 2차원 배열이기에

현재 위치 = (row * 행열의 열의 갯수) + col 이다.

 

● 참고 할 것

: 반례 및 풀이과정

https://hongjw1938.tistory.com/115

 

: 비트 옮기기

https://vixxcode.tistory.com/23

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

int paper[4][4];
int N, M, sol;


void program()
{
    // 가로 : 0 / 세로 : 1
    // 맨 처음에는 모두 가로
    for(int index = 0; index < (1 << N * M); index++)
    {
        int total = 0;
        
        // 가로 종이 조각의 총합 구하기
        for(int row = 0; row < N; row++)
        {
            // 가로 종이 조각
            int pieceRow = 0;
            
            // 가로방향으로 탐색
            for(int col = 0; col < M; col++)
            {
                // 계속 가로인 경우
                if((index & (1 << row * M + col)) == 0)
                    pieceRow = pieceRow * 10 + paper[row][col];
                // 세로를 만난 경우
                else
                {
                    total += pieceRow;
                    pieceRow = 0;
                }
            }
            
            // 마지막 가로 종이 조각까지 추가
            total += pieceRow;
        }
        
        // 세로 종이 조각의 총합 구하기
        for(int col = 0; col < M; col++)
        {
            // 세로 종이 조각
            int pieceCol = 0;
            
            // 세로방향으로 탐색
            for(int row = 0; row < N; row++)
            {
                // 계속 세로인 경우
                if((index & (1 << row * M + col)) != 0)
                    pieceCol = pieceCol * 10 + paper[row][col];
                // 가로를 만난 경우
                else
                {
                    total += pieceCol;
                    pieceCol = 0;
                }
            }
            
            // 마지막 세로 종이 조각까지 추가
            total += pieceCol;
        }
        
        // 최대값을 저장
        sol = max(sol, total);
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N >> M;
    
    // 입력되는 숫자가 연속되어있으므로
    // 문자 1개로 입력받고 숫자로 변환하여 저장
    for(int n = 0; n < N; n++)
    {
        for(int m = 0; m < M; m++)
        {
            char temp;
            cin >> temp;
            paper[n][m] = temp - '0';
        }
    }
    
    // 종이 조각 최대 총합 구하기
    program();
    
    // 최댓값 출력
    cout << sol;
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [540 - 브루트 포스 - 비트마스크] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	11723	집합	https://pirateturtle.tistory.com/265
2	1182	부분수열의 합	https://pirateturtle.tistory.com/266
3	14889	스타트와 링크	https://pirateturtle.tistory.com/267
4	14391	종이 조각	https://pirateturtle.tistory.com/268