[알고리즘 PS] 백준 14500번 테트로미노 자바 문제풀이

문제

해당 포스팅은 백준의 14500번 테트로미노 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

문제 접근

이번 문제도 완전 탐색으로 해결할 수 있는 문제이다.

어떻게 나는 완전 탐색으로 풀 수 있는 문제라고 생각했을까??

우선 주어진 문제에서 원하는 답을 찾기 위해서는 테트로미노 하나를 놓아서 최대의 합을 구해야 한다.

 

그럼 당장 생각나는 것은 n by m 크기의 배열을 하나씩 검사하면서 최대 합을 구하면 될 것 같다는 생각이 든다.

이제 여기서 이 문제를 완전 탐색으로 풀 것인가, 이분 탐색으로 풀 것인가를 정할 수 있다.

 

완탐이나 이분 탐색(혹은 다른 탐색 기법)을 구분짓는 것은 바로 시간 복잡성의 통과이다.

 

시간 복잡도를 보면 우리가 연산해야할 최악의 경우의 수가 나온다.

 

n * m 행렬에서 각 원소마다 어떤 테트로미노를 놓았는지 검사를 한다고 치면 최악의 경우 4 * 500인 2000번의 경우가 나게 된다.

 

그리고 각각의 5가지 종류의 테트로미노를 보자.

 

위의 그림과 같이 12가지의 테트로미노가 나올 수 있다.

 

그럼 아까 구했던 행렬의 최악의 경우 2000번과 19가지의 테트로미노가 각각들어갈 경우를 곱한다면 대략 456000번의 연산을 수행햐야 한다는 결과가 도출된다.

 

우리는 채점 서버가 보수적으로 봤을 때 1초에 1억번 연산을 한다고 가정했으니 24000번은 매우 작은, 한 번에 통과할 수 있는 양의 연산인 셈이다.

 

그래서 이 문제를 결국 완전 탐색으로 도출할 수 있을 것 같다는 결론이 나왔다.

오답 후보

이번 문제는 block 좌표에 대해서 실수할 수 있는 부분이 매우 많은 문제였다.

이점 유의해서 잘 풀어보자.

정답 코드

import java.util.*;
public class Main {
    static int[][][] block = {
        {{0,1}, {0,2}, {0,3}},
        {{1,0}, {2,0}, {3,0}},
        {{1,0}, {1,1}, {1,2}},
        {{0,1}, {1,0}, {2,0}},
        {{0,1}, {0,2}, {1,2}},
        {{1,0}, {2,0}, {2,-1}},
        {{0,1}, {0,2}, {-1,2}},
        {{1,0}, {2,0}, {2,1}},
        {{0,1}, {0,2}, {1,0}},
        {{0,1}, {1,1}, {2,1}},
        {{0,1}, {1,0}, {1,1}},
        {{0,1}, {-1,1}, {-1,2}},
        {{1,0}, {1,1}, {2,1}},
        {{0,1}, {1,1}, {1,2}},
        {{1,0}, {1,-1}, {2,-1}},
        {{0,1}, {0,2}, {-1,1}},
        {{0,1}, {0,2}, {1,1}},
        {{1,0}, {2,0}, {1,1}},
        {{1,0}, {2,0}, {1,-1}},
    };
    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++) {
            for (int j=0; j<m; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        int ans = 0;
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                for (int k=0; k<19; k++) {
                    boolean ok = true;
                    int sum = a[i][j];
                    for (int l=0; l<3; l++) {
                        int x = i+block[k][l][0];
                        int y = j+block[k][l][1];
                        if (0 <= x && x < n && 0 <= y && y < m) {
                            sum += a[x][y];
                        } else {
                            ok = false;
                            break;
                        }
                    }
                    if (ok && ans < sum) {
                        ans = sum;
                    }
                }
            }
        }
        System.out.println(ans);
    }
}

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.