백준 “종이 조각” 문제를 풀어보았습니다.

여기를 누르면 건너뛸 수 있습니다.

문제

영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, 열은 왼쪽부터 오른쪽까지 번호가 매겨져 있다.

영선이는 직사각형을 겹치지 않는 조각으로 자르려고 한다. 각 조각은 크기가 세로나 가로 크기가 1인 직사각형 모양이다. 길이가 N인 조각은 N자리 수로 나타낼 수 있다. 가로 조각은 왼쪽부터 오른쪽까지 수를 이어 붙인 것이고, 세로 조각은 위에서부터 아래까지 수를 이어붙인 것이다.

아래 그림은 4×4 크기의 종이를 자른 한 가지 방법이다.

https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/14391/1.png

각 조각의 합은 493 + 7160 + 23 + 58 + 9 + 45 + 91 = 7879 이다.

종이를 적절히 잘라서 조각의 합을 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 종이 조각의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 4)

둘째 줄부터 종이 조각이 주어진다. 각 칸에 쓰여 있는 숫자는 0부터 9까지 중 하나이다.

출력

영선이가 얻을 수 있는 점수의 최댓값을 출력한다.

예제 입력 1

2 3
123
312

예제 출력 1

435

예제 입력 2

2 2
99
11

예제 출력 2

182

예제 입력 3

4 3
001
010
111
100

예제 출력 3

1131

예제 입력 4

1 1
8

예제 출력 4

8

Solution

[문제 이해]

새로운 유형의 문제였고, 시간초과를 이겨내지 못해서 검색을 통해 풀이를 진행하였습니다.

  • 비트마스킹 사용 → 경우의 수를 비트를 이용해서 뽑아내어 원본 데이터를 대입하여 계산하는 방식
  • 브루트포스 사용

검색을 통해 이해한 내용을 바탕으로 코드를 작성했습니다.

[코드]

import sys
# import numpy as np
from itertools import product
input = sys.stdin.readline

def solution():
    N, M = map(int, input().split())
    board = [[int(y) for y in x] for _ in range(N) for x in input().split()]
    
    # 비트마스킹 데이터 생성
    bit_masks = product([0, 1], repeat=N*M)
    result = 0

    # 1차원 배열인 bit_mask 데이터를 2차원 배열로 변환하는 함수
    def to_matrix(arr):
        # return np.array_split(arr, N)
        return [arr[i:i+M] for i in range(0, len(arr), M)]

    # 비트마스킹 데이터에 따라 가로 -> 세로 순으로 연산
    for case in bit_masks:
        bit_mask = to_matrix(case)
        # 행과 열의 총합 변수
        rows_sum = cols_sum = 0

        # 행 연산
        for x in range(N):
            row_sum = 0
            for y in range(M):
                if bit_mask[x][y] == 0:
                    row_sum = row_sum * 10 + board[x][y]
                if bit_mask[x][y] == 1 or y == (M-1):
                    rows_sum += row_sum
                    row_sum = 0

        # 열 연산
        for y in range(M):
            col_sum = 0
            for x in range(N):
                if bit_mask[x][y] == 1:
                    col_sum = col_sum * 10 + board[x][y]
                if bit_mask[x][y] == 0 or x == (N-1):
                    cols_sum += col_sum
                    col_sum = 0

        total_sum = rows_sum + cols_sum
        result = max(result, total_sum)

    print(result)

solution()

[여담]

비트마스킹이란 문제 풀이 방식을 알게 됐습니다.

채점하던 도중 마지막에

“Python 버전을 어떤 걸 쓰길래 ModuleNotFoundError 가 뜨는 걸까?”

라는 생각이 들어서 백준 사이트는 외부(numpy) 라이브러리를 지원하지 않는다는 것을 알게 됐습니다.

Result