영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, 열은 왼쪽부터 오른쪽까지 번호가 매겨져 있다.
영선이는 직사각형을 겹치지 않는 조각으로 자르려고 한다. 각 조각은 크기가 세로나 가로 크기가 1인 직사각형 모양이다. 길이가 N인 조각은 N자리 수로 나타낼 수 있다. 가로 조각은 왼쪽부터 오른쪽까지 수를 이어 붙인 것이고, 세로 조각은 위에서부터 아래까지 수를 이어붙인 것이다.
아래 그림은 4×4 크기의 종이를 자른 한 가지 방법이다. 각 조각의 합은 493 + 7160 + 23 + 58 + 9 + 45 + 91 = 7879 이다. 종이를 적절히 잘라서 조각의 합을 최대로 하는 프로그램을 작성하시오.
입력
첫째 줄에 종이 조각의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 4) 둘째 줄부터 종이 조각이 주어진다. 각 칸에 쓰여 있는 숫자는 0부터 9까지 중 하나이다.
출력
영선이가 얻을 수 있는 점수의 최댓값을 출력한다.
📝 문제 분석
이 문제에서는 $N \times M$ 크기의 종이가 주어집니다. 각 칸에는 숫자가 적혀 있으며 종이를 겹치지 않는 조각으로 나눠야 합니다. 조각은 다음 규칙을 따라야 합니다.
✅ 규칙
조각은 가로 또는 세로로만 나눌 수 있습니다.
같은 조각 내의 숫자는 이어 붙여 하나의 숫자로 만듭니다.
조각들의 합이 최대가 되도록 합니다.
💡 해결 방법
📕 비트마스크 (Bitmask)란?
비트마스크란 이진수(0과 1)를 이용하여 여러 개의 상태를 하나의 숫자로 표현하는 방법입니다.
✅ 예제
각 자리(비트)가 0이면 OFF이고 1이면 ON을 의미합니다.
상태
이진수
십진수
0000
모든 상태 OFF
0
0001
1번 상태 ON
1
0010
1번 상태 ON
2
0011
1번, 2번 상태 ON
3
0100
3번 상태 ON
4
1111
모든 상태 ON
15
1️⃣ Step 1: 종이를 자르는 모든 경우의 수를 탐색
비트마스크를 활용하여 종이의 모든 칸을 가로 조각(1) 또는 세로 조각(0)로 설정하는 모든 경우의 수를 탐색합니다.
종이의 크기가 최대 $4 \times 4 = 16$(칸)이므로 각 칸을 0 또는 1로 표현하는 16비트($2^16 = 65536$)를 활용할 수 있습니다.
mask의 i번째 비트가 1이면 가로 조각
mask의 i번째 비트가 0이면 세로 조각
즉, 비트마스크 mask를 통해 종이를 나누는 모든 경우를 탐색할 수 있습니다.
n, m = map(int, input().split())
paper = [list(map(int, list(input().strip()))) for _ in range(n)]
# 모든 경우의 수 탐색
for mask in range(1 << (n * m)): # 2^(N*M)개의 경우의 수를 모두 탐색
print(bin(mask)) # mask를 이진수(0과 1)로 출력
✅ 예제: $2 \times 3$ 크기의 종이
1 2 3
4 5 6
이 종이의 각 칸을 비트마스크로 표현하면 다음과 같습니다.
비트마스크 값
종이 분할 방법
111000
101101
000000
111111
종이가 $N \times M$ 크기라면 모든 칸을 가로(1) 또는 세로(0)로 설정하는 경우의 수는 $2^{N \times M}$입니다. 예를 들어 $4 \times 4$ 종이라면 $2^{16} = 65536$ 가지의 경우를 탐색할 수 있습니다.
2️⃣ Step 2: 가로 조각(1) 처리
같은 행에서 연속된 1을 찾아 숫자를 이어붙여야 합니다.
중간에 세로 조각(0)이 나오면 하나의 숫자가 끝난 것으로 간주해야 합니다.
total_sum = 0 # 최종 합
for i in range(n):
current_num = 0 # 현재 가로 조각 숫자
for j in range(m):
idx = i * m + j # 비트마스크 인덱스
if mask & (1 << idx): # 가로(1)인 경우
current_num = current_num * 10 + paper[i][j] # 숫자 이어 붙이기
else:
total_sum += current_num # 현재까지 만든 숫자를 더하기
current_num = 0 # 새로운 숫자 시작
total_sum += current_num # 마지막 숫자 더하기
1 << i는 i번째 위치가 1인 비트값을 의미합니다.
mask & (1 << i)가 0이 아니면 i번째 칸이 가로(1)라는 뜻입니다.
mask & (1 << i)가 0이면 i번째 칸이 세로(0)라는 뜻입니다.
숫자를 이어붙일 때는 기존 숫자 current_num의 자릿수를 증가시키기 위해 10을 곱한 후 새로운 숫자 paper[i][j]를 더해줍니다.
3️⃣ Step 3: 세로 조각(0) 처리
같은 열에서 연속된 0을 찾아 숫자를 이어붙입니다.
중간에 가로 조각(1)이 나오면 하나의 숫자가 끝난 것으로 간주해야 합니다.
for j in range(m):
current_num = 0 # 현재 세로 조각 숫자
for i in range(n):
idx = i * m + j # 비트마스크 인덱스
if not (mask & (1 << idx)): # 세로(0)인 경우
current_num = current_num * 10 + paper[i][j] # 숫자 이어 붙이기
else:
total_sum += current_num # 현재까지 만든 숫자를 더하기
current_num = 0 # 새로운 숫자 시작
total_sum += current_num # 마지막 숫자 더하기
4️⃣ Step 4: 모든 경우의 수를 탐색하여 최댓값 찾기
모든 경우에 대해 Step 2~3을 반복하면서 최댓값을 찾습니다.
max_sum = 0 # 최댓값 저장
for mask in range(1 << (n * m)):
total_sum = 0 # 현재 경우의 조각 합
# Step 2: 가로 조각 숫자 만들기
# Step 3: 세로 조각 숫자 만들기
max_sum = max(max_sum, total_sum)
print(max_sum)
👩💻 나의 답안
n, m = map(int, input().split())
paper = [list(map(int, input())) for _ in range(n)]
max_sum = 0
for mask in range(1 << (n * m)):
total_sum = 0
# 가로 조각 숫자
for i in range(n):
current_num = 0
for j in range(m):
idx = i * m + j
if mask & (1 << idx):
current_num = current_num * 10 + paper[i][j]
else:
total_sum += current_num
current_num = 0
total_sum += current_num
# 세로 조각 숫자
for j in range(m):
current_num = 0
for i in range(n):
idx = i * m + j
if not (mask & (1 << idx)):
current_num = current_num * 10 + paper[i][j]
else:
total_sum += current_num
current_num = 0
total_sum += current_num
max_sum = max(max_sum, total_sum)
print(max_sum)
