[C++ / 백준 14391번] 종이 조각

문제

 

 

 

 

시행 착오

 

비트마스크 알고리즘을 사용해 문제 풀이가 아직 익숙치 않아 풀이가 오래 걸렸다.

무에서 유를 창조할 수는 없기에 gpt에게 아이디어만 제공받아 풀이를 시작했다.

 

 

해결 방법

 

문제에서의 힌트는 수는 무조건 행렬에서 각각 성분의 크기가 커지는 방향으로 진행된다는 점이다.

따라서 수는 오른쪽, 혹은 아래쪽 으로만 진행하게 된다. 

경우의 수가 2개라는 것은 결국 이진으로 표현이 가능함을 알 수 있었다.

 

배열 3개를 사용했다.

입력받은 수를 저장할 arr

비트마스크를 통한 경우의수를 저장할 binaryarr

방문 여부를 나타내는 visited

 

방문되어있지 않은 이진배열 위치에서 해당 위치의 값이 아닌 값 (연속되지 않을 때까지, 방문 되지 않은 곳으로) 까지 순회하면서 수를 만들고 더해준 다음 최댓값을 구했다. 

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;

int N, M;

int arr[4][4];
int binaryarr[4][4];


int main()
{
    cin >> N >> M;

   
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            scanf("%1d", &arr[i][j]);
        }
    }
 
    // 1이면 오른쪽, 0이면 아래쪽

    int maxresult = 0;
    int num = 0;
    int sum = 0;

    for (int mask = 0; mask < (1<<(N*M)); mask++)
    {

        for (int y = 0; y < N; y++)
        {
            for (int x = 0; x < M; x++)
            {

                binaryarr[y][x] = (mask >> ((M * y) + x)) & 1;
            }
        }

        bool visited[4][4] = { false };
        sum = 0;

        for (int y = 0; y < N; y++)
        {
            for (int x = 0; x < M; x++)
            {

                if (!visited[y][x])
                {
                    num = 0;
                    int a = x, b = y;

                    if (binaryarr[y][x] == 0)
                    {
                        while ( b < N && !visited[b][a] && binaryarr[b][a] == 0 )
                        {
                            num = arr[b][a] + num * 10;
                            visited[b][a] = true;
                            b += 1;
                        }

                        sum += num;
                    }
                    else
                    {
                        while ( a < M && !visited[b][a] && binaryarr[b][a] == 1 )
                        {
                            num = arr[b][a] + num * 10;
                            visited[b][a] = true;
                            a += 1;
                        }

                        sum += num;
                    }
                }
            }
        }
        maxresult = max(maxresult, sum);
    }

    cout << maxresult;
  
    return 0;
}