백준 14391 종이 조각

비트마스킹 문제 분류로 잡은 문제이다. 골드 3이라 쉽겠지... 하고 문제 생각을 했는데 뭔가 계속 안풀렸다... 허허허허

질문으로 감좀 잡아봐야겠다 했는데, 제출이 3천명이나 되는데 질문이 3개밖에 없다... 이건 무슨 일인지.

 

머리 쥐어뜯다가 검색을 해봤다. 역시 좀 신박한 접근이었다. 각 셀의 상태를 0 : 가로로 찢기, 1 : 세로로 찢기 로 표현해서 m*n 개의 상태를 순회하면서 값을 계산한다.

비트마스킹 변수 안의 각 셀 위치는 2D가 아니고 1D이므로 row*m + col 해서 해당 셀이 어떻게 찢어지는지 찾아, 가로탐색할때 가로 값을 측정하고, 세로 탐색할때 세로 값을 측정한다.

모든 경우의 수 일때, 각 row, col을 순회하며 쭉 이어지면 계속해서 숫자를 이어가고, 끊어지면 지금까지 계산한 숫자를 sum에 저장하는 방식으로 숫자들의 합을 구한다.

해당 합들의 max 값을 출력하면 답이다...

---

#include <iostream>
#include <cstring>
#include <string>

int main()
{
    int n, m;
    std::string map[4];
    std::cin >> n >> m;
    memset(map, 0, sizeof(map));
    for (int i = 0; i <n; i++)
    {
        std::string tmp;
        std::cin >> tmp;
        map[i] = tmp;
    } 
    int answer = -1;

    for (int bit = 0; bit < (1 << (m*n)); bit++) // 모든 공간 탐색
    {
        int sum = 0;

        for (int i = 0; i < n; i++)
        {
            int curnum = 0;
            for (int j = 0; j<m; j++)
            {
                int loc = i *m + j;
                if ((bit & (1<<loc)) == 0) // 이번 숫자가 가로로 이루어진 숫자일때
                    curnum = curnum * 10 + (map[i][j] - '0'); // 자리수 밀고 숫자 추가
                else
                {  
                    sum += curnum; // 지금까지 계산한것 더하기
                    curnum = 0; // 초기화
                }
            }
            sum += curnum;
        }

        for (int j = 0; j < m; j++)
        {
            int curnum = 0;
            for (int i = 0; i <n; i++)
            {
                int loc = i*m + j;
                if ((bit & (1 << loc)) != 0) // 1일때로 하면 안됨! 비트는 자리수 유지.
                    curnum = curnum * 10 + (map[i][j] - '0'); // 이번 숫자가 세로로 이루어지는 숫자일때, 자리수 밀고 숫자 추가
                else
                {
                    sum += curnum; // 지금까지 계산한 것 더하기
                    curnum = 0; // 초기화
                }
            }
            sum += curnum; // 계산해둔것 sum에 추가
        }
        answer = std::max(sum, answer); // 이번 경우의 수 max 비교
    }
    std::cout << answer;
}

 

bitmasking을 쓴다는것을 알고 있음에도, 그걸 어떻게 사용할지 떠올리는 것은 별개의 일인것 같다. 근데 약간 전체 탐색이나 어떤 상황을 표시하는데 bitmasking을 사용한다는 틀이 잡혀가는 것 같다. 다른 문제 유형도 풀어봐야겠다.

 

오늘도 평온한 하루가 되길. 슨민.