[백준] 14391번 - 종이 조각 Python, Java

문제

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

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

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

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

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

입력

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

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

출력

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

예제 입력 1

2 3
123
312

예제 출력 1

435

예제 3개는 생략

풀이

Python

import sys
input = sys.stdin.readline

n,m = map(int,input().rstrip().split())
a = [list(map(int,list(input().rstrip()))) for _ in range(n)]
ans = 0
for s in range(1<<(n*m)):
    sum = 0
    for i in range(n):
        cur = 0
        for j in range(m):
            k = i*m+j
            if (s & (1<<k)) == 0:
                cur = cur*10 + a[i][j]
            else:
                sum += cur
                cur = 0
        sum += cur
    for j in range(m):
        cur = 0
        for i in range(n):
            k = i*m+j
            if (s&(1<<k)) != 0:
                cur = cur*10 + a[i][j]
            else:
                sum += cur
                cur = 0
        sum+=cur
    ans = max(ans, sum)

print(ans)

Java

import java.util.*;
public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] a = new int[n][m];
        for (int i=0; i<n; i++) {
            String s = sc.next();
            for (int j=0; j<m; j++) {
                a[i][j] = s.charAt(j)-'0';
            }
        }
        int ans = 0;
        // 0: -, 1 : |
        for (int s=0; s<(1<<(n*m)); s++) {
            int sum = 0;
            for (int i=0; i<n; i++) {
                int cur = 0;
                for (int j=0; j<m; j++) {
                    int k = i*m+j;
                    if ((s&(1<<k)) == 0) {
                        cur = cur * 10 + a[i][j];
                    } else {
                        sum += cur;
                        cur = 0;
                    }
                }
                sum += cur;
            }
            for (int j=0; j<m; j++) {
                int cur = 0;
                for (int i=0; i<n; i++) {
                    int k = i*m+j;
                    if ((s&(1<<k)) != 0) {
                        cur = cur * 10 + a[i][j];
                    } else {
                        sum += cur;
                        cur = 0;
                    }
                }
                sum += cur;
            }
            ans = Math.max(ans,sum);
        }
        System.out.println(ans);
    }
}

정리

• 비트마스킹을 통해 총 경우의 수 (1<<(N*M))-1 가지를 돌면서 합을 구해준다.
• -(가로)의 경우에는 0으로 |(세로)의 경우에는 1로 나타낸다고 생각한다.
• k는 2차원 배열을 1차원으로 펴냈을 때의 해당 번호를 나타내며, 이 번호에 위치한 비트를 가지고 가로의 경우와 세로의 경우의 합을 구한다.