[백준] 종이 조각 14391번 (Python) -Bitmasking

문제

영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, 열은 왼쪽부터 오른쪽까지 번호가 매겨져 있다.

영선이는 직사각형을 겹치지 않는 조각으로 자르려고 한다. 각 조각은 크기가 세로나 가로 크기가 1인 직사각형 모양이다. 길이가 N인 조각은 N자리 수로 나타낼 수 있다. 가로 조각은 왼쪽부터 오른쪽까지 수를 이어 붙인 것이고, 세로 조각은 위에서부터 아래까지 수를 이어붙인 것이다.

아래 그림은 4×4 크기의 종이를 자른 한 가지 방법이다.

각 조각의 합은 493 + 7160 + 23 + 58 + 9 + 45 + 91 = 7879 이다.

종이를 적절히 잘라서 조각의 합을 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 종이 조각의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 4)

둘째 줄부터 종이 조각이 주어진다. 각 칸에 쓰여 있는 숫자는 0부터 9까지 중 하나이다.

출력

영선이가 얻을 수 있는 점수의 최댓값을 출력한다.

예제 입력 1

2 3
123
312

예제 출력 1

435

예제 입력 2

2 2
99
11

예제 출력 2

182

예제 입력 3

4 3
001
010
111
100

예제 출력 3

1131

예제 입력 4

1 1
8

예제 출력 4

8

---

풀이방법

처음 비트마스킹을 사용한 문제였다. 혼자 해결방법을 생각해냈지 못했다. 스터디를 하며 이해한 문제.

• 모든 경우의 수를 확인하기 위해선 어떻게 해야할까?
  • 종이 1칸당 가로 or 세로 2가지 경우가 들어갈 수 있다. 
  • 종이가 4*4 사이즈라면? 16개의 칸에 각각 0 또는 1이 들어가는 경우의 수 = 2^(n*m) = 2^ 16
• 다음으로는 가로로 이어지는 경우와 세로로 이어지는 경우 모두를 탐색해서 최대값을 찾아야 한다. 어떻게?
  • 2차원 배열을 1줄로 생각했을 때 인덱스를 담는다.
  •  i & (1 << idx)
    • i는 0 ~ 2^16 - 1 중 한가지 케이스값을 가질 것이고, idx만큼 leftShift하는 이유는 idx번째 칸에 종이가 가로인지 세로인지 확인하기 위해서이다. (idx는 0~15의 값을 갖는다.)
    • 예를 들어 i가 3이면 이진수(11)이고,  현재 idx가 1라면  (1 << idx)는 10 이 될것이고 이 둘은 and연산을 수행하면
    • = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0

      0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1

      0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0

    • 0이 아니게 된다.
    • (0이 아닌경우는 인경우, 0인경우는 세로인 경우로 가정한다.)
  • idx는 2차원 배열의 인덱스가 아닌 1차원으로 쭉 늘린 인덱스라는것을 생각해야한다.
  • idx를 돌면서 연속으로 가로 또는 세로가 나온다면 
    • 숫자를 붙여준다(10의 자리수씩 높여서 계산)
• 가로인 경우와 세로인 경우를 함께 탐색하며 케이스 별로 나온 누적합을 ans배열에 다 더해주고
• 정답으로 최대값을 출력한다.

import sys

input = sys.stdin.readline

# n행, m열
n, m = map(int, input().rstrip().split())

paper = []
for _ in range(n):
    paper.append(list(map(int, input().rstrip())))

ans = []

for i in range(1 << n*m):
    total = 0
    #가로합 계산
    for row in range(n):
        rowsum = 0
        for col in range(m):
            # idx는 2차원 행렬을 1줄로 만들었을때의 인덱스
            idx = row*m + col
            if i & (1 << idx) != 0: #(0아니면 가로로 더한다)
                rowsum = rowsum * 10 + paper[row][col]
            else:
                total += rowsum
                rowsum = 0
        total += rowsum

    #세로합 계산
    for col in range(m):
        colsum = 0
        for row in range(n):
            idx = row*m + col
            if i & (1 << idx) == 0: #(0이면 세로로 더한다)
                colsum = colsum * 10 + paper[row][col]
            else:
                total += colsum
                colsum = 0
        total += colsum
    ans.append(total)

print(max(ans))

 

참고 자료: https://vixxcode.tistory.com/23