https://www.acmicpc.net/problem/14391
14391번: 종이 조각
영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고,
www.acmicpc.net
직사각형 종이를 적절히 잘라 가로 조각들과 세로 조각들의 합을 최대로 만드는 문제다.
종이 조각을 자를때 특별한 규칙이 없고, 입력으로 주어지는 조각의 숫자들또한 규칙이 없으므로, 모든 경우의 수를 탐색해 해를 도출해본다.
각 조각들마다 두 가지 경우로 나뉜다.
- 가로 조각일 경우
- 세로 조각일 경우
이때 가로 조각을 0, 세로 조각을 1로 표현한다면 각 조각들마다 0 과 1의 상태를 가지게 되고, 조각의 개수는 N*M 개로, 총 2^(N*M) 가지의 경우가 존재한다.
N 과 M 이 모두 1 에서 4 사이로, 범위가 크지 않으므로, 각각의 행과 열에 해당하는 조각들을 비트로 표현한다면 최대 16자리의 비트로 나타낼 수 있다.
예를들어 N 과 M 이 모두 4라면 다음과 같이 행과 열의 비트를 나타낼 수 있을 것이다.
- 1100111100111011, 1000000011000011, 0000111101101001..
총 비트의 범위는 0000000000000000 ~ 1111111111111111 이고, 10 진수로 나타낸다면 0 ~ 2^16 -1 의 범위를 가진다.
따라서, 위 범위에 있는 모든 수에 대해 행마다 비트가 0 인 인접한 수들을 이어붙인것과, 열마다 비트가 1인 인접한 수들을 이어붙인것들의 합중 가장 큰 값을 구하면 된다.
가로로 0 인 인접한 수들을 이어붙이려면, 행을 고정하고 열에 대해 숫자들을 더해나가면 된다.
세로로 1 인 인접한 수들을 이어붙이려면, 열을 고정하고 행에 대해 숫자들을 더해나가면 된다.
코드로 나타내보면 아래와 같다.
from sys import stdin
N, M = map(int, stdin.readline().split())
matrix = [list(map(int, stdin.readline().rstrip())) for _ in range(N)]
max_s = 0
for case in range(1 << M*N):
s = 0
# 가로로 0 인것들의 합
for i in range(N):
r = 0
for j in range(M):
bit = i*M + j
if not case & 1 << bit:
r = r*10 + matrix[i][j]
else:
s += r
r = 0
s += r
# 세로로 1 인것들의 합
for j in range(M):
c = 0
for i in range(N):
bit = i*M + j
if case & 1 << bit:
c = c*10 + matrix[i][j]
else:
s += c
c = 0
s += c
max_s = max(max_s, s)
print(max_s)