[python] 백준 14391 종이 조각

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

14391번: 종이 조각

 

 

문제 해결

우선 비트마스크에 대해서 알아야 한다.

비트마스크는 숫자를 이진수로 배열함으로써 계산을 더 빠르게 할 수 있고

bool 연산도 빠르게 할 수 있다. (1은 True, 0은 False를 나타낸다.)

비트마스크의 연산은 크게 5가지가 있다.

• AND 연산 (&) (예시 : 11011 & 10001 = 10001)
• OR 연산(|)  (예시 : 11001 & 10011 = 11011)
• XOR 연산(^) (예시 11011 ^ 10011 = 01000)
• NOT 연산(~) (예시: ~11011 = 00100)
• 시프트(Shift) 연산 (<<, >>) (예시 : 11011 <<2 = 1101100, 11011>>2 = 110))

여기서 이진수를 나타내려고 하는 이유는 bool연산을 이용하기 위해서이다.

각 원소는 가로, 또는 세로로 조각이 이어진다. 가로로 이어지면 1, 세로로 이어지면 0이라고 하자.

 

그런데 우리는 종이에 각각의 원소만 주어지고 어떻게 이어지는지는 나오지 않고 단순히 잘라진 종이의 수의 합이 최댓값이 나오도록 자르는 것이다.

이는 모든 경우를 다 계산을 해야한다. (모든 경우는 1<<n*m가지, 총 $2^{n \times m}$ 가지

따라서 처음에 각 행(가로)로 숫자를 읽어가며 가로로 이어지는 경우 계산하고 각 열(세로)로 숫자를 읽어가며 세로로 이어지는 경우를 계산한 다음 나온 합이 최대가 나오는 것을 뽑아내도록 한다.

위의 그림을 예시로

1행 => 1, 1, 1,0  (+493), 2행 => 0, 0, 1, 0, (+9), 3행 => 0, 0, 0, 0 , 4행 => 1, 1, 0, 0 (+91)

1열 1, 0, 0, 1 (+23) => 2열 1, 0, 0, 1 (+58) => 3열 1, 1, 0, 0 (+45) => 4열 0, 0, 0, 0 (+7160)  

CODE

import sys
input = sys.stdin.readline

n, m = map(int, input().split()) # 세로, 가로 크기

board = [list(map(int,input().rstrip())) for _ in range(n)]
ans = []

def solve():
    result = 0
    for i in range(1<<n*m): # pow(2,n*m)
        total = 0
        for row in range(n): # (row+1)번째 행을 본다.
            rowsum = 0
            for col in range(m): #(row+1)번째 행 (col+1)번째 열을 본다.
                idx = row*m + col # idx는 (row+1,col+1) 원소
                if i & (1 << idx ) != 0: # (i와 1<<idx의 교집합이 0아니면 가로로 더한다.)
                    rowsum = rowsum*10 + board[row][col]
                else:
                    print(i, (1<<idx))
                    total += rowsum
                    rowsum = 0
            total += rowsum

        # 세로합 계산
        for col in range(m):
            colsum = 0
            for row in range(n):
                idx = row*m + col
                if i & (1 << idx) == 0: #(0이면 세로로 더한다.)
                    colsum = colsum*10 + board[row][col]
                else:
                    total += colsum
                    colsum = 0
            total += colsum
        ans.append(total)
    return max(ans)

print(solve())