[코테] 백준 비트마스크 14391번 문제

14391번 : 종이 조각

문제 링크

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

문제 설명

영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, 열은 왼쪽부터 오른쪽까지 번호가 매겨져 있다.

영선이는 직사각형을 겹치지 않는 조각으로 자르려고 한다. 각 조각은 크기가 세로나 가로 크기가 1인 직사각형 모양이다. 길이가 N인 조각은 N자리 수로 나타낼 수 있다. 가로 조각은 왼쪽부터 오른쪽까지 수를 이어 붙인 것이고, 세로 조각은 위에서부터 아래까지 수를 이어붙인 것이다.

아래 그림은 4×4 크기의 종이를 자른 한 가지 방법이다.

각 조각의 합은 493 + 7160 + 23 + 58 + 9 + 45 + 91 = 7879 이다.

종이를 적절히 잘라서 조각의 합을 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 종이 조각의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 4)

둘째 줄부터 종이 조각이 주어진다. 각 칸에 쓰여 있는 숫자는 0부터 9까지 중 하나이다.

출력

영선이가 얻을 수 있는 점수의 최댓값을 출력한다.

문제풀이

최대 4x4의 크기라 시간 제한에는 안걸리게 작성할 수는 있으나 막상 구현하려니 까다로운 문제였다.

기본 아이디어는 배열을 1차원으로 생각하여 0000 0000 0000 0000 ~ 1111 1111 1111 1111 까지의 모든 수를 비트마스킹 기법으로 순회하면서 0이면 세로 1이면 가로로 수를 계산하여 최대가 되는 합을 출력하면 된다.

아래는 참고한 블로그 https://jemarque.tistory.com/entry/%EB%B0%B1%EC%A4%80python-14391%EB%B2%88-%EC%A2%85%EC%9D%B4%EC%A1%B0%EA%B0%81

def calculate() :
    answer = 0
    
    for bit in range(1 << (N * M)) :
        total = 0
        
        for i in range(N) :
            sum1 = 0
            for j in range(M) :
                idx = i * M + j
                if bit & (1 << idx) != 0 :
                    sum1 = sum1 * 10 + arr[i][j]
                else :
                    total += sum1
                    sum1 = 0
            total += sum1

        for j in range(M) : 
            sum2 = 0
            for i in range(N) :
                idx = i * M + j
                if bit & (1 << idx) == 0:
                    sum2 = sum2 * 10 + arr[i][j]
                else :
                    total += sum2
                    sum2 = 0
            total += sum2

        answer = max(answer, total)
    return answer

N, M = map(int, input().split())
arr = [list(map(int, input())) for _ in range(N)]
print(calculate())