[BOJ] 14500번: 테트로미노

출처 : https://www.acmicpc.net/problem/14500

14500번: 테트로미노

 

 

 

1. 문제 설명 

다음 조건을 만족하고, 테트로미노 하나를 적절히 놓아서 놓인 칸에 쓰여 있는 수들의 합이 최대가 하는 값을 구한다.

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸에 포함해야 하며, 회전이나 대칭이 가능하다.

• 정사각형은 서로 겹치면 안 된다.
• 도형은 모두 연결되어 있어야 한다.
• 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

 

 

2. 접근 방식 

가능한 모든 모양의 경우의 수에 대한 좌표를 만들어서 브루트포스로 접근하였다.

 

 

 

3. 주석 달기 (변수 설명, 각 줄마다 문장으로 설명, 함수 설명)

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static FastReader scan = new FastReader();
    static int n, m, ans = 0;
    static ArrayList<Integer>[] matrix;

    static int[][][] tetris = {{{0, 0}, {0, 1}, {0, 2}, {0, 3}},
                                {{0, 0}, {1, 0}, {2, 0}, {3, 0}},
                                {{0, 0}, {1, 0}, {0, 1}, {1, 1}},
                                {{0, 0}, {1, 0}, {2, 0}, {2, 1}},
                                {{0, 1}, {1, 1}, {2, 1}, {2, 0}},
                                {{0, 0}, {0, 1}, {1, 1}, {2, 1}},
                                {{0, 0}, {0, 1}, {1, 0}, {2, 0}},
                                {{0, 0}, {1, 0}, {1, 1}, {1, 2}},
                                {{0, 2}, {1, 1}, {1, 2}, {1, 0}},
                                {{0, 0}, {0, 1}, {0, 2}, {1, 2}},
                                {{0, 0}, {1, 0}, {0, 1}, {0, 2}},
                                {{0, 0}, {1, 0}, {1, 1}, {2, 1}},
                                {{0, 1}, {1, 1}, {1, 0}, {2, 0}},
                                {{1, 0}, {1, 1}, {0, 1}, {0, 2}},
                                {{0, 0}, {0, 1}, {1, 1}, {1, 2}},
                                {{0, 1}, {1, 0}, {1, 1}, {1, 2}},
                                {{0, 0}, {0, 1}, {0, 2}, {1, 1}},
                                {{0, 0}, {1, 0}, {1, 1}, {2, 0}},
                                {{0, 1}, {1, 1}, {1, 0}, {2, 1}}
                                };

    static int calculate(int[][] dist) {
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int total = 0;
                int cnt = 4;
                for(int k = 0; k < 4; k++) {
                    int nx = i + dist[k][0];
                    int ny = j + dist[k][1];
                    if(0 <= nx && nx < n && 0 <= ny && ny < m) {
                        total += matrix[nx].get(ny);
                        cnt--;
                    }
                }
                if(cnt > 0) continue;
                else res = Math.max(total, res);
            }
        }
        return res;
    }
    public static void main(String[] args) {
        n = scan.nextInt(); m = scan.nextInt();
        matrix = new ArrayList[n];

        for (int i = 0; i < n; i++) {
            matrix[i] = new ArrayList<>();
            for (int j = 0; j < m; j++) {
                matrix[i].add(scan.nextInt());
            }
        }
        for (int i = 0; i < tetris.length; i++) {
            int tmp = calculate(tetris[i]);
            ans = Math.max(tmp, ans);
        }
        System.out.println(ans);
    }
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

 

4. 분석 및 시간복잡도 

시간 복잡도 : O(N * M * 19) = O(N * M)