[백준 문제] 14391번 종이 조각 (파이썬)
[백준 문제] 14391번 종이 조각 (파이썬)
[백준 문제] 14391번 종이 조각를 풀어본다.
의식의 흐름
- 일단 간헐적 재택근무로 인한 뇌기능 저하로 인하여 치매 예방겸 일끝나고 알고리즘문제를 풀려했으나 뇌 과부화로 뇌정지. 구글링으로 ‘종이 조각 파이썬’을 찾아봤으나 파이썬으로 푼 명인 실종. ㅜ.ㅜ
- 비트마스크로 문제를 풀면 된다는건 알았음.
- 근데 [[0,0,1,0], [0,0,1,1]] 이랑 [[0,0,1,0], [0,0,1,0]] 이랑 같은거 아냐? 라는 궁금증 폭발
- 같을수도있지라고 타협을 내림
- itertools라는 모듈을 알고 순열 비스무리한 문제에 대해 생긴 암 다 나음. 참고 : itertools를 이용한 문제 풀이
문제 풀이 순서
- 비트마스크를 2차원 리스트로 만든다.
- 가로 : 0을 만나면 진짜 값 저장. 옆으로 가고 또 0이면 이전것에 10을 곱해주고 저장. 만약에 1을 만나면 합계에 저장해주고 저장한거 0으로 만들고 다시 시작. 만약에 맨 마지막 열을 만나면 그냥 저장
- 세로 : 가로와 마찬가지로 만듦
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 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)
a = itertools.product([0, 1], repeat=n*m)
ans = 0
# 가로부터 합계를 구해주고 세로 합계 구해줘서 더함
for x in a:
bit_mask = to_matrix(x, m)
sumh = 0
for i in range(n):
hori = 0
for j in range(m):
if bit_mask[i][j] == 0:
hori = 10 * hori + x_lst[i][j]
if bit_mask[i][j] == 1 or j == m - 1:
sumh = sumh + hori
hori = 0
sumv = 0
for j in range(m):
vert = 0
for i in range(n):
if bit_mask[i][j] == 1:
vert = 10 * vert + x_lst[i][j]
if bit_mask[i][j] == 0 or i == n - 1:
sumv = sumv + vert
vert = 0
sum_all = sumh + sumv
ans = max(ans, sum_all)
print(ans)
