[BaekJoon] 14391 종이조각

🔦 문제 링크

✍️ 나의 풀이

---

• 빠른 계산을 위해 1과 0으로 나눠 가로와 세로를 비트마스크로 표현한다.

• 모든 경우의 수는 배열이 가질 수 있는 모든 경우이다.

• 따라서 (1 << n*m) 이라고 볼 수 있다.

• 2차원 배열을 비트마스크로 표현했으므로i*m+j의 식을 이용해 모든 위치를 검사한다.

• 가로의 경우 한 행이 끝나면 더하거나 한 행 계산 중 세로가 나오면 합에 더해주도록 한다.

🛠 나의 코드

---

# bitmask

n, m = map(int, input().split())
arr = [list(map(int, list(input()))) for _ in range(n)]
k = 0
mx = -1
while k < (1 << (n*m)):
    sm = 0
    # 가로 - 0
    for i in range(n):
        caro = 0
        for j in range(m):
            if (1 << i*m+j) & k == 0:
                caro = caro*10 + arr[i][j]
            else:
                sm += caro
                caro = 0
        sm += caro

    # 세로 - 1
    for j in range(m):
        sero = 0
        for i in range(n):
            if (1 << i*m+j) & k > 0:
                sero = sero*10 + arr[i][j]
            else:
                sm += sero
                sero = 0
        sm += sero

    mx = max(mx, sm)
    k += 1

print(mx)

📝 정리

---

• 2차원 배열을 1차원 배열로 표현한 후 비트로 표현하는 법
• 비트마스크를 이용한 가로와 세로 구분
• 가로와 세로 & 행과 열의 관계

🎈 참고

---

regularmember 블로그