백준 14391번 파이썬 문제풀이(브루트 포스 - 종이 조각)

---

코드

import itertools

# input
n, m = map(int, input().split())
x_lst = []
for _ in range(n):
    x_lst.append(list(map(int, (input()))))


# matrix 1d -> 2d convert(비트마스크를 입력받은 행렬과 같은 모양으로 변형)
def bitmask_to_matrix(l, m):
    return [l[i:i + m] for i in range(0, len(l), m)]


# itertools의 product를 이용해서 비트마스크 제너레이터 만들기
# e.g) (0,0,0,0), (0,0,0,1) ... (1,1,1,1) 0,1 을 reapeat개수만큼 반복해서 뽑아준다.
bitmask = itertools.product([0, 1], repeat=n * m)
ans = 0

# 가로부터 합계를 구해주고 세로 합계 구해줘서 더함
for x in bitmask:
    # 비트마스크를 N*M 행렬로 변환
    bitmask_matrix = bitmask_to_matrix(x, m)

    # 가로합 저장
    sum_width = 0

    # 가로 계산
    for i in range(n):
        temp_width = 0
        for j in range(m):
            if bitmask_matrix[i][j] == 0:
                temp_width = 10 * temp_width + x_lst[i][j]
            if bitmask_matrix[i][j] == 1 or j == m - 1:
                sum_width = sum_width + temp_width
                temp_width = 0

    # 세로합 저장
    sum_height = 0

    # 세로 계산
    for j in range(m):
        temp_height = 0
        for i in range(n):
            if bitmask_matrix[i][j] == 1:
                temp_height = 10 * temp_height + x_lst[i][j]
            if bitmask_matrix[i][j] == 0 or i == n - 1:
                sum_height = sum_height + temp_height
                temp_height = 0

    #가로계산과 세로계산의 합 저장
    sum_all = sum_width + sum_height

    #최대값으로 계속 변경
    ans = max(ans, sum_all)

print(ans)

-> 비트마스크를 이용해서 푸는 문제이다. 우선 비트마스크(0,1 로 이루어진 행렬)를 입력받은 행렬과 같은 형태로 만들어준다. 여기서 입력받은 행렬의 크기 만큼 0,1로 이루어질 수 있는 모든 경우의 수를 다 뽑아 내야한다.

 

그 후 뽑아놓은 비트마스크들을 반복문으로 돌며 0일 때는 가로값을 계산해 가로값에다 더해주고 1일때는 세로값만 계산하며 세로값들을 더해주어 그 두개의 값을 더하여 계속해서 최대값으로 저장하는 방식으로 문제를 풀어야 한다.