[알고리즘/백준] 14391번 : 종이 조각(python)

비트마스킹 개념을 잘 몰라서 너무 힘들었다.

처음에는 그냥 N자리를 가지면 그 수가 가장 크다고 생각했다. 하지만 예외도 있었다.

비트마스킹을 사용하려면 2차원을 1차원으로 바꿔야한다.

나는 가로를 1 세로를 0으로 두고 했다.
만약에 1111 0000 0000 0000 이면 맨 첫줄 4자리가 선택이 된다.
1000 1000 1000 1000 -> 맨 왼쪽 4자리
이런 방식으로 1부터 N * M 까지 다 비교하면 된다.

N, M = map(int, input().split())
a = [list(map(int, input()))for _ in range(N)]
ans = 0

for i in range(1 << N * M):
    tmp = 0
    for row in range(N):
        r = 0
        for col in range(M):
            idx = row * M + col

            if i & (1 << idx) != 0:
                r = r * 10 + a[row][col]
            else:
                tmp += r
                r = 0
        tmp += r
    for col in range(M):
        c = 0
        for row in range(N):
            idx = row * M + col

            if i & (1 << idx) == 0:
                c = c * 10 + a[row][col]
            else:
                tmp += c
                c = 0
        tmp += c

    if ans < tmp:
        ans = tmp

print(ans)