14391: 종이 조각

• 직사각형을 조각들로 자르는 걸 구현하는게 감이 안잡혔음 -> bitmasking을 처음 이용해봄
• 입력받은 Paper를 1차원으로 indexing 함 -> 조각들로 자르는 모든 경우의 수 = 2 ^ (N * M)
• 가로방향 확인: i & (1 << idx) != 0인 경우 / 세로방향 확인: i & (1 << idx) == 0인 경우
• bit들에서 가로방향:1, 세로방향: 0

import sys

tmp = list(map(int, sys.stdin.readline()[:-1].split(' ')))
N = tmp[0]; M = tmp[1]
P = []
for _ in range(N):
    P.append(list(map(int, sys.stdin.readline()[:-1])))

max_value = 0
def bitmask():
    global max_value
    for i in range(1 << N*M):
        local_sum = 0

        for x in range(N):
            x_sum = 0
            for y in range(M):
                idx = x * M + y
                if i & (1 << idx) != 0:
                    print("가로방향", i, x, y, idx, P[x][y])
                    x_sum = x_sum * 10 + P[x][y]
                else:
                    local_sum += x_sum; x_sum = 0
            local_sum += x_sum

        for y in range(M):
            y_sum = 0
            for x in range(N):
                idx = x * M + y
                if i & (1 << idx) == 0:
                    print("세로방향", i, x, y, idx, P[x][y])
                    y_sum = y_sum * 10 + P[x][y]
                else:
                    local_sum += y_sum; y_sum = 0
            local_sum += y_sum

        max_value = max(max_value, local_sum)

bitmask()
print(max_value)

• 출력 예시

2 2
99
11
세로방향 0 0 0 0 9
세로방향 0 1 0 2 1
세로방향 0 0 1 1 9
세로방향 0 1 1 3 1
가로방향 1 0 0 0 9
세로방향 1 1 0 2 1
세로방향 1 0 1 1 9
세로방향 1 1 1 3 1
가로방향 2 0 1 1 9
세로방향 2 0 0 0 9
세로방향 2 1 0 2 1
세로방향 2 1 1 3 1
가로방향 3 0 0 0 9
가로방향 3 0 1 1 9
세로방향 3 1 0 2 1
세로방향 3 1 1 3 1
가로방향 4 1 0 2 1
세로방향 4 0 0 0 9
세로방향 4 0 1 1 9
세로방향 4 1 1 3 1
가로방향 5 0 0 0 9
가로방향 5 1 0 2 1
세로방향 5 0 1 1 9
세로방향 5 1 1 3 1
가로방향 6 0 1 1 9
가로방향 6 1 0 2 1
세로방향 6 0 0 0 9
세로방향 6 1 1 3 1
가로방향 7 0 0 0 9
가로방향 7 0 1 1 9
가로방향 7 1 0 2 1
세로방향 7 1 1 3 1
가로방향 8 1 1 3 1
세로방향 8 0 0 0 9
세로방향 8 1 0 2 1
세로방향 8 0 1 1 9
가로방향 9 0 0 0 9
가로방향 9 1 1 3 1
세로방향 9 1 0 2 1
세로방향 9 0 1 1 9
가로방향 10 0 1 1 9
가로방향 10 1 1 3 1
세로방향 10 0 0 0 9
세로방향 10 1 0 2 1
가로방향 11 0 0 0 9
가로방향 11 0 1 1 9
가로방향 11 1 1 3 1
세로방향 11 1 0 2 1
가로방향 12 1 0 2 1
가로방향 12 1 1 3 1
세로방향 12 0 0 0 9
세로방향 12 0 1 1 9
가로방향 13 0 0 0 9
가로방향 13 1 0 2 1
가로방향 13 1 1 3 1
세로방향 13 0 1 1 9
가로방향 14 0 1 1 9
가로방향 14 1 0 2 1
가로방향 14 1 1 3 1
세로방향 14 0 0 0 9
가로방향 15 0 0 0 9
가로방향 15 0 1 1 9
가로방향 15 1 0 2 1
가로방향 15 1 1 3 1
182

• (다음에 다시 풀어봐야할듯 bitmasking으로 푸는 방식이 아직 익숙하지가 않음)