[JAVA] 14391 - 종이 조각 💛3 : 문제에서 주어지는 단어에 현혹되면 미궁으로 빠지는 문제. 본질을 위한 풀이를 작성하라!

들어가며

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

주어지는 사각형을 원하는 1 * Y 혹은 X * 1로 잘라서 모든 직사각형의 합의 최댓값을 구하면 되는 문제이다. 딱 읽었을 때는.. 음~ 완탐문제 같은데..? 라는 생각을 가지고 풀이에 들어갔다... 재귀적 흐름을 코드를 나타내기 너무너무 어려웠던 문제기에 글을 써본다.

본문으로

일단 처음에는 가로의 경우의 수를 다 채운다음 남은 빈곳을 세로 경우의 수로 채워야겠다! 라고 생각하고 아래 풀이를 작성했다...(자세히는 보지 않아도 된다. 출력도 안되는 코드이다.. 그냥 이렇게 생각했었다.. 정도로 보면 된다.)

public class Main {

    static int Y, X, ret;
    static String[][] maps;
    static int[][] visited;
    static List<Integer> sumList;

    // 가로 경우의 수 채우기
    static void goRow(int hereX, int hereY, boolean isQuad, int[][] visited, String here) {
        if (hereX >= X) {
            if (isQuad) { // 끝까지 왔는데 사각형중이라면 정답에 담기
                sumList.add(Integer.parseInt(here));
            }
            if (hereY >= Y) { // 모든 행 돌았으면 남은 열까지 채우러 가자.
                goColumn(0, 0, false, visited, "");
                int sum = 0;
                for (int i = 0; i < sumList.size(); i++) {
                    sum += sumList.get(i);
                }
                ret = Integer.max(ret, sum);
                sumList = new ArrayList<>();
                return;
            }
            goRow(0, hereY + 1, false, visited, "");
            return;
        }

        // 이번 거 사각형 포함 o
        visited[hereY][hereX] = 1;
        here += maps[hereY][hereX];
        goRow(hereX + 1, hereY, true, visited, here);
        // 이번 거 사각형 포함 x
        here += maps[hereY][hereX];
        if (isQuad) { // 만약 사각형 중이었다면 총합 값으로 담아야함
            sumList.add(Integer.parseInt(here));
        } // 아니면 비워두고 열로 채울거임
        visited[hereY][hereX] = 0;
        here = "";
        goRow(hereX + 1, hereY, false, visited, here);

    }

    // 남은 열 채우기
    static void goColumn(int hereX, int hereY, boolean isQuad, int[][] visited, String here) {
        if (visited[hereY][hereX] != 0 && !here.isBlank()) { // 지금게 방문했으면 담기
            sumList.add(Integer.parseInt(here));
            goColumn(hereX, hereY + 1, false, visited, "");
        }
        if (hereY >= Y) {
            if (isQuad) {
                sumList.add(Integer.parseInt(here));
            }
            if (hereX >= X) { // 다 돌았으면 리턴
                return;
            }
            goColumn(hereX + 1, 0, false, visited, "");
            return;
        }

        if (visited[hereY][hereY] == 0) {
            here += maps[hereY][hereX];
            visited[hereY][hereX] = 1;
            goColumn(hereX, hereY + 1, true, visited, here);
        }


    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        Y = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
        maps = new String[Y][X];
        visited = new int[Y][X];

        for (int i = 0; i < Y; i++) {
            String[] input = bf.readLine().split("");
            for (int j = 0; j < X; j++) {
                maps[i][j] = input[j];
            }
        }

        sumList = new ArrayList<>();
        ret = Integer.MIN_VALUE;
        goRow(0, 0, false, visited, "");

        System.out.println(ret);
    }
}

그렇다. 잘못된 출력이나 시간초과여도 괜찮으니 어떻게든 출력을 뽑아보려 했는데 실패했다..

---

다른분들의 코드를 훔쳐본 결과 이 문제는 아래처럼 정리될 수 있다.

악필이라..ㅎㅎ 정리하자면 여태까지 나는 "직접 직사각형을 만드는 경우의 수를 모조리 구하려고 했었다." 이 생각은 너무 코드로 구현하기 어렵고, "각 칸을 구분하여 가로인지 세로인지 정해주면 된다" 정도로 아이디어를 좁힐 수 있다.

각 칸의 경우의 수는 가로 or 세로 두가지뿐이니, 비트마스킹을 활용하여 아래와 같은 로직을 구현했다. 모든 경우에 수에 대해 가로 세로를 각각 따로 세주면서, 가로를 셀때 해당 칸이 가로일때(s & (1 << k) == 0)와 아닐때를 구분하여 합을 구해준다.

public class Main {

    static int Y, X, ret;
    static int[][] maps;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        Y = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
        maps = new int[Y][X];

        for (int i = 0; i < Y; i++) {
            String input = bf.readLine();
            for (int j = 0; j < X; j++) {
                maps[i][j] = input.charAt(j) - '0';
            }
        }
        ret = 0;

        for (int s = 0; s < (1 << Y * X); s++) {
            int sum = 0;
            // 가로 계산
            for (int i = 0; i < Y; i++) {
                int cur = 0;
                for (int j = 0; j < X; j++) {
                    int k = i * X + j;
                    if ((s & (1 << k)) == 0) {
                        cur = cur * 10 + maps[i][j];
                    } else {
                        sum += cur;
                        cur = 0;
                    }
                }
                sum += cur;
            }

            // 새로 계산
            for (int j = 0; j < X; j++) {
                int cur = 0;
                for (int i = 0; i < Y; i++) {
                    int k = i * X + j;
                    if ((s & (1 << k)) != 0) {
                        cur = cur * 10 + maps[i][j];
                    } else {
                        sum += cur;
                        cur = 0;
                    }
                }
                sum += cur;
            }
            ret = Math.max(sum, ret);
        }

        System.out.println(ret);

    }
}

---

각 칸을 구분한다는 아이디어만 떠올린다면, 경우의 수는 가로 세로 두가지뿐이고 입력값도 매우 작기에 쉽게 비트마스킹을 떠올릴 수 있겠지만, 보통 코테에서는 결국 시간에 쫓겨 아이디어도 생각안하고 완탐을 돌리게 되는 경우가 있다. 나라면 이 문제를 코테에서 마주쳤을 때 입력값이 매우 작으므로 시간복잡도 생각도 안하고 그냥 완탐 풀이를 했을 것이다. 

재귀적으로 완탐풀이를 제출한다면, 아래처럼 구현할 수 있겠다.

public class Main {

    static int Y, X, ret;
    static int[][] maps;
    static int[][] type; // 가로 0, 세로 1

    static void dfs(int idx) {
        if (idx == Y * X) {
            calc();
            return;
        }

        int y = idx / X;
        int x = idx % X;  // 이 아이디어 좋다,,,

        type[y][x] = 0; // 가로 선택
        dfs(idx + 1);

        type[y][x] = 1; // 세로 선택
        dfs(idx + 1);
    }

    static void calc() {
        int sum = 0;

        // 가로 세기
        for (int i = 0; i < Y; i++) {
            int cur = 0;
            for (int j = 0; j < X; j++) {
                if (type[i][j] != 0) {
                    cur = cur * 10 + maps[i][j];
                } else {
                    sum += cur;
                    cur = 0;
                }
            }
            sum += cur;
        }
        // 새로 세기
        for (int j = 0; j < X; j++) {
            int cur = 0;
            for (int i = 0; i < Y; i++) {
                if (type[i][j] != 1) {
                    cur = cur * 10 + maps[i][j];
                } else {
                    sum += cur;
                    cur = 0;
                }
            }
            sum += cur;
        }

        ret = Math.max(ret, sum);
    }


    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        Y = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
        maps = new int[Y][X];
        type = new int[Y][X];

        for (int i = 0; i < Y; i++) {
            String input = bf.readLine();
            for (int j = 0; j < X; j++) {
                maps[i][j] = input.charAt(j) - '0';
            }
        }

        ret = Integer.MIN_VALUE;
        dfs(0);
        System.out.println(ret);

    }
}

마무리하며

사실 이 문제 처음 읽었을 때, 너무 간단해 보여서 꼭 내 힘으로 풀어야겠다 다짐하고 계속 붙잡았다.. 그랬더니 3시간이 지났다...ㅜㅜ 너무 억울해서 이러한 thinking을 꼭 기억해야겠다. 

1. 문제에서 사각형을 언급해서 자꾸 사각형을 진짜 만드려고 하다보니 풀이 자체가 너무 어려워졌다. -> 문제에서 주어진 단어에 현혹되지 말고 문제 풀이를 위한 본질을 생각하자. 이 문제는 각 칸이 가로인지 세로인지만 구분하면 사각형은 생각할 필요도 없는 문제였다.

 

2. 2차원 좌표를 1차원으로 바꾸기 -> 비트연산자를 활용하다보면 이차원 배열의 각 경우의 수를 하나의 정수로 저장하기 때문에 1차원으로 나타내야한다. 문제에서 쓴 int k = i * X + j; 이런 표현 잊지말자.

 

3. 특히 이차원 배열의 Y와 X를 나타낼때 정수하나로만 나타낸다면 int y = idx / X;    int x = idx % X;   이렇게 나타내는 아이디어 너무 유용한 것 같다!