[BruteForce] 백준 14500: 테트로미노

14500번: 테트로미노 (acmicpc.net)

14500번: 테트로미노

처음에 문제를 보고 숨이 탁 막혔다. 나는 아직도 종이찢어서 칸 채우기, 칠교블록 놓기 비스무리한 문제들... 그런 문제들을 너무 어려워한다.

 

그런데 문제를 다시 자세히 읽어 보니 보드에 블록 단 하나!!! 를 놓고 그 블록이 점유하는 칸들의 숫자 합이 가장 큰 경우를 찾는 문제였다.

 

이렇게 되면 사실 어려울 것이 없다. 블록의 첫칸부터 끝칸까지, 각 블록들을 넣어보고 그 블록이 칸에 들어갈 수 있으면 그 칸들의 숫자합을 계산하고 지금까지의 가장 큰 숫자합과 비교하여 업데이트하고, 만일 들어갈 수 없으면 그냥 패스하면 된다.

 

보드가 가장 큰 경우는 500*500 = 250,000칸, 그리고 블록의 회전과 대칭을 허용하기 때문에 블록의 경우의 수는 다음과 같다.

• 한 일자
• 아라비아 일자
• 2*2 정사각형
• ㄴ자
• 역 ㄴ자
• ㄱ자
• 역ㄱ자
• 세로 번개 모양(그림으로 주어진 오리지널)
• 세로 번개 모양 좌우대칭
• 가로 번개 모양
• 가로 번개 모양 좌우대칭
• ㅜ
• ㅗ
• ㅏ
• ㅓ

그림으로 직접 그려서 포스팅하려다가... 너무 귀찮았다. 아무튼 블록의 경우의 수는 이상 15개. 즉 250,000*15번 테스트하는 경우가 최악의 경우인데 이 경우의 수도 bruteforce 를 시전하기에는 넉넉하다.

 

이제 이 이후로는 그냥 구현에서 실수만 하지 않도록 하면 된다. 내 경우는 블록을 테스트할 때 최대한 좌측, 최대한 상단을 기준으로 하여 최대한 헷갈리지 않게 했다.

 

문답무용. 코드로 마무리한다. 

 

import java.io.*;

public class Main {
    static int N,M;
    static int[][] board;
    static int maxSum;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] NM = br.readLine().split(" ");
        N = Integer.parseInt(NM[0]);
        M = Integer.parseInt(NM[1]);

        board = new int[N][M];
        for(int i=0;i<N;i++){
            String[] input = br.readLine().split(" ");
            for(int j=0;j<M;j++){
                board[i][j] = Integer.parseInt(input[j]);
            }
        }

        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                int sum, sum2 = 0;
                //세로 1자
                if(i<=N-4){
                    sum = board[i][j]+board[i+1][j]+board[i+2][j]+board[i+3][j];
                    maxSum = Math.max(sum,maxSum);
                    sum = 0;
                }

                //가로 1자
                if(j<=M-4){
                    sum = board[i][j]+board[i][j+1]+board[i][j+2]+board[i][j+3];
                    maxSum = Math.max(sum,maxSum);
                    sum = 0;
                }

                //2*2
                if(i<=N-2&&j<=M-2){
                    sum = board[i][j]+board[i+1][j]+board[i][j+1]+board[i+1][j+1];
                    maxSum = Math.max(sum,maxSum);
                    sum=0;
                }

                //ㄴ, 역 ㄱ
                if(i<=N-3&&j<=M-2){
                    sum = board[i][j]+board[i+1][j]+board[i+2][j]+board[i+2][j+1];
                    sum2 = board[i][j]+board[i+1][j]+board[i+2][j]+board[i][j+1];
                    maxSum = Math.max(maxSum,Math.max(sum,sum2));
                    sum = sum2 = 0;
                }

                //ㄱ,역ㄴ
                if(i<=N-3&&j>=1){
                    sum = board[i][j]+board[i+1][j]+board[i+2][j]+board[i][j-1];
                    sum2 = board[i][j]+board[i+1][j]+board[i+2][j]+board[i+2][j-1];
                    maxSum = Math.max(maxSum,Math.max(sum,sum2));
                    sum = sum2 = 0;
                }

                //가로 ㄴ, 가로 역ㄴ
                if(i>=1&&j<=M-3){
                    sum = board[i][j]+board[i][j+1]+board[i][j+2]+board[i-1][j];
                    sum2 = board[i][j]+board[i][j+1]+board[i][j+2]+board[i-1][j+2];
                    maxSum = Math.max(maxSum,Math.max(sum,sum2));
                    sum = sum2 = 0;
                }

                //가로 ㄱ, 가로 역 ㄱ
                if(i<=N-2&&j<=M-3){
                    sum = board[i][j]+board[i][j+1]+board[i][j+2]+board[i+1][j];
                    sum2 = board[i][j]+board[i][j+1]+board[i][j+2]+board[i+1][j+2];
                    maxSum = Math.max(maxSum,Math.max(sum,sum2));
                }
                //세로벼락
                if(i<=N-3&&j<=M-2){
                    sum = board[i][j]+board[i+1][j]+board[i+1][j+1]+board[i+2][j+1];
                    maxSum = Math.max(maxSum,sum);
                    sum = 0;
                }
                //세로벼락 대칭형
                if(i<=N-3&&j>=1){
                    sum = board[i][j]+board[i+1][j]+board[i+1][j-1]+board[i+2][j-1];
                    maxSum = Math.max(maxSum,sum);
                    sum = 0;
                }
                //가로벼락
                if(i<=N-2&&j<=M-3){
                    sum = board[i][j]+board[i][j+1]+board[i+1][j+1]+board[i+1][j+2];
                    maxSum = Math.max(maxSum,sum);
                    sum = 0;
                }
                //가로벼락 대칭형
                if(i>=1&&j<=M-3){
                    sum = board[i][j]+board[i][j+1]+board[i-1][j+1]+board[i-1][j+2];
                    maxSum = Math.max(maxSum,sum);
                    sum = 0;
                }
                //ㅜ
                if(i<=N-2&&j<=M-3){
                    sum = board[i][j]+board[i][j+1]+board[i][j+2]+board[i+1][j+1];
                    maxSum = Math.max(maxSum,sum);
                    sum = 0;
                }
                //ㅗ
                if(i>=1&&j<=M-3){
                    sum = board[i][j]+board[i][j+1]+board[i][j+2]+board[i-1][j+1];
                    maxSum = Math.max(maxSum,sum);
                    sum = 0;
                }
                //ㅏ
                if(i<=N-3&&j<=M-2){
                    sum = board[i][j]+board[i+1][j]+board[i+2][j]+board[i+1][j+1];
                    maxSum = Math.max(maxSum,sum);
                    sum = 0;
                }
                //ㅓ
                if(i<=N-3&&j>=1){
                    sum = board[i][j]+board[i+1][j]+board[i+2][j]+board[i+1][j-1];
                    maxSum = Math.max(maxSum,sum);
                    sum = 0;
                }
            }

        }
        System.out.println(maxSum);
    }
}