[완탐] 종이 조각 - java

Seunghyeon·2025년 3월 5일
0

백준 문제 푼다.

목록 보기
21/21

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

종이를 여러 조각으로 잘라서 합을 구하는 문제


<풀이 방법>

1차 풀이 방법 - 시간 초과

dfs

각 칸에서 가로길이, 세로길이 가능한 만큼 확인하고 dfs로 다음 칸으로 넘어간다.

  • 시간초과 이유 =>

n,m 이 4,4 일 때 한 칸에서 고려하는 경우의 수 = (가로 0,1,2,3) + (세로 0,1,2,3) = 8

탐색할수록 경우의 수는 줄어들긴 하지만 경우가 제곱으로 커짐

또한 계산하지 않아도 되는 경우까지 계산하게 됨.

-> 한 줄에 가로2칸 + 가로2칸 이면 따로 계산하는게 아니라
가로4칸으로 계산해서 하나로 이은 값이 더 크다.

2차 풀이 방법 - 정답

마찬가지로 dfs 이지만

각 칸을 가로칸으로 배치할 것인지 세로칸으로 배치할 것인지 정한다.

모든 칸을 전부 정했으면 붙어있는 칸이 같은칸이면 자릿수를 올려가며 더해주기.


<시간 초과>

import java.util.*;
import java.io.*;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb;
    static StringTokenizer st;

    static int n, m, count, max = Integer.MIN_VALUE;
    static int[][] arr;
    static int[][] visited;

    // 오른쪽, 아래쪽만 고려
    static int[] dx = {1, 0};
    static int[] dy = {0, 1};

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new int[n][m];
        visited = new int[n][m];

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

        dfs(0, 0, 0, 0);

        System.out.println(max);
    }

    static void dfs(int depth, int sum, int x, int y) {
        // 모든 칸을 전부 확인 했으면 합 계산
        if (depth == n * m) {
            if (sum > max) max = sum;
            return;
        }

        for (int i = x ; i < n ; i ++) {
            for (int j = (i == x ? y : 0) ; j < m ; j ++) {
                if (visited[i][j] == -1) {
                    // 세로로 얼마나 갈 지 정해서 가기
                    for (int h = 0 ; h < n - i ; h ++) {
                        // 이미 다른 종이 조각이 있으면 안됨.
                        if (avail(i, j, h, 0)) {
                            int val = chkLine(i, j, h, 0, count++);
                            dfs(depth + h + 1, sum + val, i, j);
                            chkLine(i, j, h, 0, -1);
                            count --;
                        }
                    }
                    // 가로로 얼마나 갈 지
                    for (int w = 0 ; w < m - j ; w ++) {
                        if (avail(i, j, w, 1)) {
                            int val = chkLine(i, j, w, 1, count++);
                            dfs(depth + w + 1, sum + val, i, j);
                            chkLine(i, j, w, 1, -1);
                            count --;
                        }
                    }
                }
            }
        }

    }

    // 갈 수 있는곳인지 검증하고 들어와야 함.
    // dir: 0 => 아래쪽, dir: 1 => 오른쪽
    static int chkLine(int x, int y, int len, int dir, int count) {
        int sum = 0;
        int temp = (int)Math.pow(10, len);

        for (int i = 0 ; i < len + 1 ; i ++) {
            int nx = x + dx[dir] * i;
            int ny = y + dy[dir] * i;
            visited[nx][ny] = count;

            sum += arr[nx][ny] * temp;
            temp /= 10;
        }

        return sum;
    }

    static boolean avail(int x, int y, int len, int dir) {
        for (int i = 0 ; i < len + 1 ; i ++) {
            int nx = x + dx[dir] * i;
            int ny = y + dy[dir] * i;

            if (visited[nx][ny] != -1) return false;
        }

        return true;
    }

}


<정답 코드>

import java.util.*;
import java.io.*;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    static int n, m, max = 0;
    static int[][] arr;
    static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new int[n][m];
        visited = new boolean[n][m];

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

        dfs(0, 0);

        System.out.println(max);
    }

    // 각 칸에 대해 가로/세로 선택
    static void dfs(int x, int y) {
        if (x == n) {
            calc();
            return;
        }

        int nextX = x;
        int nextY = y + 1;
        if (nextY == m) {
            nextX++;
            nextY = 0;
        }

        // 가로 조각으로 선택
        visited[x][y] = true;
        dfs(nextX, nextY);

        // 세로 조각으로 선택
        visited[x][y] = false;
        dfs(nextX, nextY);
    }

    // 종이 조각 합계 계산
    static void calc() {
        int sum = 0;

        // 가로 조각 계산
        for (int i = 0; i < n; i++) {
            int temp = 0;
            for (int j = 0; j < m; j++) {
                if (visited[i][j]) { // 가로 조각
                    temp = temp * 10 + arr[i][j];
                } else {
                    sum += temp;
                    temp = 0;
                }
            }
            sum += temp; // 줄 끝나면 더하기
        }

        // 세로 조각 계산
        for (int j = 0; j < m; j++) {
            int temp = 0;
            for (int i = 0; i < n; i++) {
                if (!visited[i][j]) { // 세로 조각
                    temp = temp * 10 + arr[i][j];
                } else {
                    sum += temp;
                    temp = 0;
                }
            }
            sum += temp; // 줄 끝나면 더하기
        }

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

profile
그냥 합니다.

0개의 댓글