[Baekjoon] 14391번 종이 조각

문제

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

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

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

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

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

입력

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

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

출력

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

예제

Example 1:

Input: 
2 3
123
312
Output: 
435

Example 2:

Input:
2 2
99
11
Output:
182

Example 3:

Input:
4 3
001
010
111
100
Output:
1131

Example 4:

Input:
1 1
8
Output:
8

조건

시간 제한 : 2초

메모리 제한 : 512 MB

풀이과정

풀이 1

포인트는 각 칸마다 가로와 세로로 나누어주고, 해당 경우마다 값을 구해서 업데이트해주는 것이다.

n, m = map(int, input().split())

graph = []

for _ in range(n):
    graph.append(list(map(int,input())))

ans = 0

def dfs(arr):
    global ans
    sub = 0
    if len(arr) == n*m:

        narr = []
        for i in range(n):
            narr.append(arr[i*m:i*m+m])

        # 가로
        for i in range(n):
            aa = 0
            for j in range(m):
                if narr[i][j] == 0:
                    aa = aa * 10 + graph[i][j]
                else:
                    sub += aa
                    aa = 0
            sub += aa
            aa = 0
        # 세로
        for j in range(m):
            bb = 0
            for i in range(n):
                if narr[i][j] == 1:
                    bb = bb*10 + graph[i][j]
                else:
                    sub += bb
                    bb = 0
            sub += bb
            bb = 0
        ans = max(ans,sub)
        return
    else:
        dfs(arr+[0])
        dfs(arr+[1])

dfs([])
print(ans)