문제 설명

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

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

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

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

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

입력 조건

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

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

출력 조건

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

전체 코드

import sys

n, m = list(map(int, sys.stdin.readline().split()))

arr = [[0] * m for _ in range(n)]

for i in range(n):
    data = list(map(int, sys.stdin.readline().rstrip()))
    for j in range(m):
        arr[i][j] = data[j]

HORIZONTAL = 0
VERTICAL = 1

answer = 0


def calculate_result(result: list) -> int:
    values = []
    # 가로 방향으로 진행하면서 수평인 것들 계산하기
    for x in range(n):
        value = 0
        for y in range(m):
        	# 연속으로 수평이라면, 이어 붙인다.
            if result[x][y] == HORIZONTAL:
                value *= 10
                value += arr[x][y]
            else:
            	# 끊어 졌으면, 이전 까지 이어 붙인 것을 담는다. 그리고 값을 초기화한다.
                if value != 0:
                    values.append(value)
                value = 0
        if value != 0:
            values.append(value)

    # 세로로 진행하면서 수직인 것들 계산하기
    for y in range(m):
        value = 0
        for x in range(n):
        	# 연속으로 수직이라면, 이어 붙인다.
            if result[x][y] == VERTICAL:
                value *= 10
                value += arr[x][y]
            else:
            	# 끊어 졌으면, 이전 까지 이어 붙인 것을 담는다. 그리고 값을 초기화한다.
                if value != 0:
                    values.append(value)
                value = 0
        if value != 0:
            values.append(value)

    score = sum(values)
    return score


# n과 m은 최대 4이기 때문에 재귀를 활용할 수 있다.
# 재귀를 이용하여 [i][j]가 가로 방향인지, 세로 방향인지 결정해 놓자.
def recursion(x: int, y: int, result: list):
    global answer
    # 행의 끝 이후에 도달하면, 기저 조건 도달
    if x >= n:
        answer = max(answer, calculate_result(result))
        return
    # 열의 끝 이후에 도달하면, 다음 행으로 가보자.
    elif y >= m:
        recursion(x + 1, 0, result)
    else:
        result[x][y] = HORIZONTAL
        recursion(x, y + 1, result)

        result[x][y] = VERTICAL
        recursion(x, y + 1, result)


recursion(0, 0, [[0] * m for _ in range(n)])

print(answer)

해설

1<=N,M<=4이기 때문에, 재귀를 활용하여 N X M 배열의 상태를 다르게 나타낼 수 있다. 예를 들어, 2 X 2 이차원 배열에 대해 0 또는 1로 재귀를 하게 되면 다음과 같은 상태들을 얻을 수 있다.

[[0,0],[0,0]]
[[0,0],[0,1]]
[[0,0],[1,0]]

...

[[1,1],[1,1]]

각 분기의 기저 조건에 도달하면 위와 같은 배열 상태들을 얻을 수 있다.

해당 상태에 대해 가로 방향으로 진행하면서 연속적으로 수평인 것은 이어 붙이고, 수평이 끊어진 것은 그대로 값을 담는다.
세로 방향 역시 연속적으로 수직인 것은 이어 붙이고, 수직이 끊어진 것은 그대로 값을 담는다.

참고

https://whereisusb.tistory.com/230