문제:
영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, 열은 왼쪽부터 오른쪽까지 번호가 매겨져 있다.
영선이는 직사각형을 겹치지 않는 조각으로 자르려고 한다. 각 조각은 크기가 세로나 가로 크기가 1인 직사각형 모양이다. 길이가 N인 조각은 N자리 수로 나타낼 수 있다. 가로 조각은 왼쪽부터 오른쪽까지 수를 이어 붙인 것이고, 세로 조각은 위에서부터 아래까지 수를 이어붙인 것이다.
아래 그림은 4×4 크기의 종이를 자른 한 가지 방법이다.
각 조각의 합은 493 + 7160 + 23 + 58 + 9 + 45 + 91 = 7879 이다.
종이를 적절히 잘라서 조각의 합을 최대로 하는 프로그램을 작성하시오.
입력:
첫째 줄에 종이 조각의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 4)
둘째 줄부터 종이 조각이 주어진다. 각 칸에 쓰여 있는 숫자는 0부터 9까지 중 하나이다.
출력:
영선이가 얻을 수 있는 점수의 최댓값을 출력한다.
풀이방법:
비트마스킹을 사용하여 해당 문제를 풀었다. N*M의 크기의 직사각형을 0,1의 비트마스킹으로 표현한다. 이 때 0은 가로로 연결되는 경우를 의미하고, 1은 세로로 연결되는 경우를 의미하게 된다.
주어진 케이스에 대해 가로와 각각 따로 계산을 수행하도록 한다. 가로는 idx가 0인 경우에 대해서만 이어붙이며 값을 누적시키도록 한다. 반대로 세로는 idx가 1인 경우에 대해서만 이어붙이고 값을 누적시킨다. 모든 케이스에 대해서 이 작업을 반복 수행하며 가장 큰 경우를 출력하도록 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
from itertools import product
h, w = map(int, input().split())
mat = []
for i in range(h):
mat.append(list(map(int,list(input()))))
idxs = product(range(2),repeat=h*w)
ans = 0
for idx in idxs:
tmp = 0
for i in range(h):
sum_ = 0
for j in range(w):
k = i*w+j
if idx[k]==0:
sum_ = 10*sum_+mat[i][j]
else:
tmp+=sum_
sum_ = 0
if sum_!=0:
tmp+=sum_
for i in range(w):
sum_ = 0
for j in range(h):
k = i+j*w
if idx[k]==1:
sum_ = 10*sum_+mat[j][i]
else:
tmp+=sum_
sum_ = 0
if sum_!=0:
tmp+=sum_
if tmp > ans:
ans = tmp
print(ans)
|
cs |
문제링크:
https://www.acmicpc.net/problem/14391
14391번: 종이 조각
영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고,
www.acmicpc.net
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]20056. 마법사 상어와 파이어볼 (0) | 2021.11.02 |
|---|---|
| [BOJ]11058. 크리보드 (0) | 2021.11.01 |
| [BOJ] 2251. 물통 (0) | 2021.10.28 |
| [BOJ] 15988. 1, 2, 3 더하기 (0) | 2021.10.25 |
| [BOJ] 13023. ABCDE (0) | 2021.10.22 |