처음엔 4x4 크기가 정해져있기 때문에 그냥 브루트포스로 풀면 풀릴 것이라 생각했지만.. 구현 자체가 막막했다.
칸마다 가로/세로/확장안함 3가지 경우를 나누고 접근했지만 틀렸다.
더 고민해본 후 풀이방법을 찾아봤는데 비트마스크를 써서 풀더라.
칸마다 가로/세로로 나눠 2가지 경우를 두고 NxM 칸이 모두 2가지 경우를 가지니 2^(NxM)-1의 경우를 갖는다. 이 2^(NxM)-1의 경우를 모두 순회하며 가로/세로일때로 경우를 또 나눠 가로칸, 세로칸의 합을 구한다.
2^(NxM)-1개의 경우를 순회하며 각 칸이 가로/세로인지 판단할 때 shift 연산과 & 연산을 활용한다.
N, M = map(int, input().split())
arr = [list(map(int, input())) for _ in range(N)]
def bf():
result = 0
for i in range(1 << N * M):
total = 0
for row in range(N):
srow = 0
for col in range(M):
idx = row * M + col
if i & (1 << idx) != 0: srow = srow * 10 + arr[row][col]
else:
total += srow
srow = 0
total += srow
for col in range(M):
scol = 0
for row in range(N):
idx = row * M + col
if i & (1 << idx) == 0: scol = scol * 10 + arr[row][col]
else:
total += scol
scol = 0
total += scol
result = max(result, total)
return result
print(bf())
와~