14391 종이조각

1. 문제

2. 코드

def check():
    global maxval
    #비트마스크로 2^(N*M)의 경우의 수를 다 따져본다. 
    for state in range(1<<N*M):
        total = 0
        #가로 숫자의 합
        for row in range(N):
            rowsum = 0
            for col in range(M):
                idx = row*M + col
                #가로일 때(1)
                if state & (1<<idx) != 0:
                    rowsum = rowsum*10 + paper[row][col]
                else:
                    total += rowsum
                    rowsum = 0
            #모든 칸을 다 검사하고 마지막 더한 값도 추가해준다.
            total += rowsum
 
        
        #세로 숫자의 합
        for col in range(M):
            colsum = 0
            for row in range(N):
                idx = row*M + col
                #세로일 때(0)
                if state & (1<<idx) == 0:
                    colsum = colsum * 10 + paper[row][col]
                else:
                    total += colsum
                    colsum = 0
            total += colsum
        maxval = max(maxval,total)
        
            
N, M = map(int,input().split())
paper = [[int(i) for i in input()]for _ in range(N)]
maxval = 0
check()
print(maxval)
 

3. 후기

이 문제의 핵심은 모든 칸마다 가로인지 세로인지 0과 1을 이용해서 나타낸다는 것이다.

한 칸마다 가로와 세로 두 가지 경우의 수가 있으므로 모든 칸의 경우의 수는 총 2^(N*M)이다. 

0과 1을 비트마스크로 표현하였다. 그래서 만약 3X3 행렬이 있으면 000000000 부터 111111111까지 검사해서 최대값을 뽑아낸다. 

다른 블로그에서는 이해하기 쉽도록 재귀로 풀었는데 비트마스크를 공부해 볼겸 첫번째 블로그를 참조하였다.