14391번 종이조각 백준 파이썬

문제:www.acmicpc.net/problem/14391

14391번: 종이 조각

이 문제는 비트마스크의 개념을 정확히 몰랐을 때라 그런지 감이 전혀 안왔다.

처음에는 그냥 우선 자릿수가 큰 게 더 크므로 가로로 싹 다 더한 값과 세로로 싹 다 더한 값 중 큰 거 아닐까 하는 생각을 했지만 역시 예외는 있었다.

 

def bitmask():
    global maxAns
    # 비트마스크로 2^(N*M)의 경우의 수를 따져본다
    for i in range(1 << n * m):
        total = 0
        # 가로 합 계산
        for row in range(n):
            rowsum = 0
            for col in range(m):
                # idx 는 이차원 배열을 일렬로 늘렸을때의 인덱스가 어디인지 의미
                idx = row * m + col
                # 가로일때
                if i & (1 << idx) != 0:
                    rowsum = rowsum * 10 + arr[row][col]
                # 세로일때 앞에서 나온 수를 total에 더하고 rowsum 초기화
                else:
                    total += rowsum
                    rowsum = 0
            total += rowsum

        # 세로 합 계산
        for col in range(m):
            colsum = 0
            for row in range(n):
                # idx 는 이차원 배열을 일렬로 늘렸을때의 인덱스가 어디인지 의미
                idx = row * m + col
                # 세로일때
                if i & (1 << idx) == 0:
                    colsum = colsum * 10 + arr[row][col]
                # 가로일때 앞에서 나온 수를 total에 더하고 colsum 초기화
                else:
                    total += colsum
                    colsum = 0
            total += colsum
        maxAns = max(maxAns, total)


n, m = map(int, input().split())

arr = [list(map(int, input())) for _ in range(n)]

maxAns = 0
bitmask()
print(maxAns)
​

참고:https://kyun2da.github.io/2020/09/26/paperPiece/

[백준/Python] 14391 종이 조각 - Kyun's 개발 기록일지

 

 

위의 그림은 2x2 의 경우를 예를 들었다.

1인 경우를 가로 0인 경우를 세로로 하였다. 그리고 값의 가중치는 위의 코드를 보면 알 수 있다.

전체의 경우의수는 1<<n*m이다. 왜냐하면 한 칸당 가로 또는 세로로 갈 수 있는 경우의 수가 있으므로 2를 n*m번을 곱한 것이 전체 경우의 수이기 때문이다.

그래서 가로를 확인하는 것은 i & (1 << idx) != 0: 으로 하였다. 가로의 경우에는 ---> 방향으로 읽어야 하기때문에 for문이 row 다음에 col 순으로 되어있다. 그리고 순서가 2차원 배열로 되어있으므로 이것을 비트로 다시 표현해야 한다.

이때 순서는 [0][0],[0][1],[0][2],[1][0],[1][1] 이런식으로 쭉 펼쳐놓았다고 생각하면 된다.

그리고 나서 합계를 통해 최대값을 도출해내면 된다.