백준_14391_종이조각

문제

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

14391번: 종이 조각

풀이

 

1) 비트 마스킹

행렬의 각 칸은 "가로, 세로" 두가지 중 한 상태를 가질 수 있다. 예를 들어서, 아래와 같이  표현할 수 있다.

따라서, 이진수를 사용하면 16칸에 가로와 세로를 채우는 모든 경우를 쉽게 구할 수 있다.

이를 위해서 세로를 0, 가로를 1이라고 정한다. 

 

2) 브루스포트

2진수로 만든 배열이 가지는 값을 연산한다.

위의 예시처럼 "가로" 상태를 가지는 값끼리, "세로" 값을 가지는 값끼리 묶어서 연산한다.

아래 코드에서는 문자열을 이용해서 해결했다. (아래에서 ^기호는 spacebar를 의미)

코드

N, M = map(int, input().strip().split())
board = [list(map(int, input().strip())) for i in range(N)]
vertical = '0'
horizental = '1'

# 2. 2진수 배열을 연산하기
def getScore(dirBoard) : 
    # horizental
    string = ""
    for i in range(N) : 
        string += " "
        for j in range(M) :
            if dirBoard[i][j]==horizental : string += str(board[i][j])
            else : string += " "
            
    # vertical
    string += " "
    for j in range(M) : 
        string += " "
        for i in range(N) : 
            if dirBoard[i][j]==vertical : string += str(board[i][j])
            else : string += " "  
    
    return sum(map(int, string.split()))

# 1. 2진수로 1부터 2**16까지 만들기
MAXNUM = 2**(N*M)
ans = 0
for i in range(0, MAXNUM) : 
    dirBoard = bin(i+MAXNUM)[3:]
    # reshape (1, N*M) → (N, M) 
    dirBoard = [dirBoard[i:i+M] for i in range(0, M*N, M)]
    ans = max(ans, getScore(dirBoard))
print(ans)