[파이썬(Python)] 백준 14391번 종이 조각 - 비트마스크

 

 

백준 14391번: 종이 조각

문제 바로 가기

---

📌 문제

영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 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)

 

Algorithm/백준/Gold/14391. 종이 조각 at main · kuun1000/Algorithm