우주의 IT 소행성

https://www.acmicpc.net/problem/14391

n, m = map(int, input().rstrip().split())
a = [list(map(int, input())) for _ in range(n)]
ans = 0
for s in range(1 << (n * m)): # n * m 사이즈의 비트마스크
    sum = 0
    for i in range(n):
        cur = 0
        for j in range(m):
            k = i * m + j # row major order
            if (s & (1 << k)) == 0: # 가로일 경우
                cur = cur * 10 + a[i][j]
            else:
                sum += cur
                cur = 0
        sum += cur
    for j in range(m):
        cur = 0
        for i in range(n):
            k = i * m + j
            if (s & (1 << k)) != 0: # 세로일 경우
                cur = cur * 10 + a[i][j]
            else:
                sum += cur
                cur = 0
        sum += cur
    ans = max(ans, sum)
print(ans)

- 가로 조각과 세로 조각 두가지로 나뉨
- o과 1로 나누어진 NM개의 칸으로 생각 (max 16개)
- 4X4 공간을 1차원으로 이어붙여 생각 (max 16칸, 16자리 비트로 표현)

1. 비트마스크를 이용해 모든 경우를 구하고
2. 수의 합을 구해주면 된다

-A[I][J] -> i*m+j (row major order)

비트 마스크에 대해 오늘 공부하기 시작했는데,

문제에서는 뭐 배열의 최대 값을 구하라는데 2^n -1 을 왜 차곡차곡넣고있지? 라고 생각했었다.

비트 값으로 연산을 하자는게 아니라

비트를 통해 현재 상태를? 구분짓자는 내용이라는걸 깨달은 순간 문제가 보이기 시작했다.

비트 마스크 (Bitmask)

- 0 부터 N - 1 까지 정수로 이루어진 집합을 나타낼 때 사용

- 공간을 매우 절약할 수 있음

- 각종 연산을 조금 변형해서 사용해야 함

- 집합 값의 검사, 추가, 제거의 모든 복잡도가 O(1)임

A << B -> 비트를 왼쪽으로 한 칸 씩 미는 작업으로, A * 2^B과 같은 뜻

A >> B -> 비트를 오른쪽으로 한 칸 씩 미는 작업으로, A / 2^B과 같은 뜻

집합의 값을 검사, 추가, 제거 할 수 있음.

비트마스크 S에 X가 있는지 검사 ( AND 연산 )

- S & (1 << X) == 0 이면 없음, 0이 아니면(1<<X)이면 있음

비트마스크 S에 X를 추가 (OR 연산)

- 이미 있는 수를 또 추가할 때는 무시. (1 OR 1 = 1이기 때문)

-  S | (1 << X) 하는 것

비트 마스크 S에 X를 제거

- AND 연산일 경우 지우려는 값만 0으로 대조시키면 무조건 0으로

- S & ~(1 << X)

토글 연산

- 0 < - > 1 SWAP 연산

- S ^ (1 << X)

전체 집합

- (1 << N) - 1

공집합

- 0

비트 연산의 연산자 우선 순위를 잘 생각해야 한다.

- 비트 연산은 사칙연산보다 후순위 연산 순위를 가진다.