[BOJ / C++] 백준 14391 종이 조각

문제

https://www.acmicpc.net/problem/14391

 

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

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

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

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

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

입력

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

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

출력

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

---

풀이

비트마스킹을 사용하여 종이를 자르는 모든 경우의 수를 찾을 수 있다.

가로로 자를 숫자 위치는 0으로, 세로로 자를 숫자 위치는 1로 나타낸다.

n * m 크기의 숫자 입력이 있으므로, 2차원에서 비트마스킹을 구해야한다.

 

1차원의 비트마스킹 시에는 (벡터에 들어있는 데이터 뽑기 등) 이중 for문을 사용해서 처리했었는데

2차원이라서 삼중 for문을 사용했다.

 

1. 제일 밖에서는 모든 n*m의 모든 경우의 수이기 때문에 1 << (n*m) 만큼 반복해야한다.

2.  k = i*m+j 즉 왼쪽 상단부터 칸의 번호를 매기는 k값을 사용해서 뽑을 수 있다.

3. (s & (1 << k) 를 통해 뽑은 위치의 값을 찾고 값이 0(가로)일 때는 값을 누적해서 더한다. 

    1(세로)일 때는 그 위치의 값만 더하고 초기화한다. 

    예를 들어  (0 0 1 0 0)이고 (4 8 9 1 2) 일 때, 1인 위치 전까지 더하고 48 + 9 + 12 이런 형식이 되는 것이다.

 

2, 3 과정을 세로 블럭을 더하기 위해서 반복한다. 

 

그리고 한 s를 돌 때마다 sum과 최대값을 비교해서 갱신한다.

 // N * M 모든 좌표 경우의 수 (가로 블럭->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++) {
                // k = 왼쪽 상단부터 칸 번호
                // 1 2 3
                // 4 5 6
                int k = i * m + j;

                // 해당 위치가 0이면 (가로 블럭) 누적해서 더하기 4 8 = 40 + 8
                if ((s & (1 << k)) == 0) {
                    cur = cur * 10 + a[i][j];
                } else {
                    // 해당 위치가 1이면 (세로 블럭) 더하기 중단
                    sum += cur;
                    cur = 0;
                }
            }
            sum += cur;
        }

 

전체 풀이

#include <bits/stdc++.h>

using namespace std;

int n, m;
int a[5][5];

int main() {
    int n, m;
    int ans = 0;

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        string line;
        cin >> line;
        for (int j = 0; j < m; j++) {
            a[i][j] = line[j] - '0';
        }
    }

    // N * M 모든 좌표 경우의 수 (가로 블럭->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++) {
                // k = 왼쪽 상단부터 칸 번호
                // 1 2 3
                // 4 5 6
                int k = i * m + j;

                // 해당 위치가 0이면 (가로 블럭) 누적해서 더하기 4 8 = 40 + 8
                if ((s & (1 << k)) == 0) {
                    cur = cur * 10 + a[i][j];
                } else {
                    // 해당 위치가 1이면 (세로 블럭) 더하기 중단
                    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;
                // 해당 위치가 1이면 (세로 블럭) 누적해서 더하기 4 8 = 40 + 8
                if ((s & (1 << k)) != 0) {
                    cur = cur * 10 + a[i][j];
                } else {
                    // 해당 위치가 0이면 (가로 블럭) 더하기 중단
                    sum += cur;
                    cur = 0;
                }
            }
            sum += cur;
        }
        ans = max(ans, sum);
    }
    cout << ans;

    return 0;
}