알고리즘 풀이 - 백준 14391(종이 조각, 완전 탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

 

NxM크기의 직사각형 종이를 갖고 있고 그 안에 NxM개의 숫자가 쓰여져 있을 때, 1xK 또는 Kx1형태로 종이를 부분으로 찢었을 때, 찢긴 종이의 숫자가 이어진 것으로 본다면 전체 합이 가장 커지는 경우를 찾는 문제

 

 

2. 풀이

 

단순히 생각하면 N과 M중 큰 숫자를 찾아 큰 숫자로 숫자가 이어지게끔 하여 종이를 찢으면 될 것처럼 보인다.

왜냐하면, N=4이고, M=3일 때, N을 기준으로 이으면 4자리수가 되고 M을 기준으로 이으면 3자리수가 될 것이기 때문이다. N=M이라면 두 경우를 비교하면 되기도 하다.

 

그런데 이 경우에는 예외가 있다. 아래의 경우를 보자.

 

위와 같은 경우, 가로 방향으로 이어 4개로 찢으면 1 + 1001이 되고 세로 방향으로 이어 4개로 찢어도 1 + 1001이 된다.

그런데!, 아래와 같이 찢으면 어떻게 될까?

 

위와 같이 찢으면 100 + 1001이 되어 1101이 최대값이 된다. 그래서 위와 같은 반례가 있어 단순히 가로 혹은 세로 방향으로만 문제를 해결할 수 없다.

 

 

이 문제는 비트마스크를 통해 반복문으로 해결할 수 있다.

만약 2x2의 경우라면 비트가 4개가 되는데 0을 가로로 찢는 경우, 1을 세로로 찢는 경우라고 가정하고 1열로 늘어놓으면 0000 ~ 1111까지가 경우의 수가 된다.

그러면 이 때, 각 경우를 체크하여 가로로 찢어진 경우에는 0으로 이어진 경우를 수로 잇고, 세로로 찢어진 경우에는 1로 이어진 경우를 수로 이어서 합을 구하면 된다.

 

자세한 것은 코드를 통해 확인해보자.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

import java.io.*;

public class Main{
    static int n;
    static int m;
    static int[][] paper;
    static int ans = 0;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] line = br.readLine().split(" ");
        n = Integer.parseInt(line[0]);
        m = Integer.parseInt(line[1]);
        paper = new int[n][m];


        for(int i=0; i < n; i++){
            String str = br.readLine();
            for(int j=0; j < m; j++){
                paper[i][j] = str.charAt(j) - '0';
            }
        }

        // 가로로 이어지면 0, 세로로 이어지면 1이라고 가정하자.
        // n*m이 주어지므로 n*m-1번 << 연산을 하면 모든 비트가 1이 되는 경우를 찾을 수 있다.
        // i = 0이면 모두 가로로만 찢는 경우이며, 모두 1이면 세로로만 찢는 경우이다.
        for(int i=0; i < (1 << n*m); i++){
            int sum = 0;

            // 현재 가로로 찢는 경우의 합을 구한다.
            for(int j=0; j < n; j++){
                int cur = 0;
                for(int k=0; k < m; k++){

                    // 현재 체크하고자 하는 위치를 l에 저장
                    int l = j*m+k;

                    // 비트를 통해 현재 위치가 0이면 가로로 찢는 부분임을 확인
                    // 가로로 찢는 것이 이어지는 동안 한 자리수씩 더 커지므로 10을 곱하고
                    // 현재 값을 더한다.
                    if((i & (1 << l)) == 0){
                        cur = cur * 10 + paper[j][k];
                        // 그 외의 경우에는 세로로 이어지는 것이므로 그냥 더하고 현재 값은 0으로 초기화
                    } else {
                        sum += cur;
                        cur = 0;
                    }
                }

                // 세로로 찢는 경우를 만나지 못한 경우 마지막에 더해주어야 한다.
                sum += cur;
            }

            // 동일하게 이번에는 세로로 찢는 경우를 모두 찾아서 더한다.
            for(int j=0; j < m; j++){
                int cur = 0;
                for(int k=0; k < n; k++){
                    // 비트 위치 확인
                    int l = j*m+k;

                    // 현재 위치가 0이 아니라면 세로로 찢긴 부분임.
                    if((i & (1 << l)) != 0){
                        cur = cur * 10 + paper[j][k];
                    } else {
                        sum += cur;
                        cur = 0;
                    }
                }

                // 가로로 찢는 경우를 만나지 못한 경우 마지막에 더해주어야 한다.
                sum += cur;
            }
            ans = Math.max(ans, sum);
        }

        bw.write(String.valueOf(ans));
        bw.flush();
        br.close();
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.