백준 14500 : 테트로미노

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

14500번: 테트로미노

[ 문제풀이 ]

테트로미노로 만들 수 있는 모든 종류(회전, 대칭)를 만들어 종이에 놓을 수 있는 모든 경우의 수를 구하면 해결할 수 있는 문제이다.

​종이를 회전시키는 방법도 있고 여러 가지 방법이 있겠지만 나는 간단하게 테트로미노로 만들 수 있는 모든 종류를 미리 만들어서 해결하였다.

​대칭, 회전을 통한 만들 수 있는 모든 종류는 다음과 같다.

이를 3차원 배열로 표현하면 다음과 같다.

static int[][][] tetromino = {{{1,1,1,1}}, {{1},{1},{1},{1}}, {{1,1},{1,1}},
				{{1,1,1},{0,1,0}}, {{0,1},{1,1},{0,1}}, {{0,1,0},{1,1,1}}, {{1,0},{1,1},{1,0}},
				{{1,0},{1,0},{1,1}}, {{1,1,1},{1,0,0}}, {{1,1},{0,1},{0,1}}, {{0,0,1},{1,1,1}},
				{{0,1},{0,1},{1,1}}, {{1,0,0},{1,1,1}}, {{1,1},{1,0},{1,0}}, {{1,1,1},{0,0,1}},
				{{1,0},{1,1},{0,1}}, {{0,1,1},{1,1,0}}, {{0,1},{1,1},{1,0}}, {{1,1,0},{0,1,1}}};

이를 가지고 종이에 놓을 수 있는 모든 경우의 수를 구하면 된다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;

	static int N, M, answer;
	static int[][] map;

	//테트로미노 모든 종류
	static int[][][] tetromino = {{{1,1,1,1}}, {{1},{1},{1},{1}}, {{1,1},{1,1}},
								  {{1,1,1},{0,1,0}}, {{0,1},{1,1},{0,1}}, {{0,1,0},{1,1,1}}, {{1,0},{1,1},{1,0}},
								  {{1,0},{1,0},{1,1}}, {{1,1,1},{1,0,0}}, {{1,1},{0,1},{0,1}}, {{0,0,1},{1,1,1}},
								  {{0,1},{0,1},{1,1}}, {{1,0,0},{1,1,1}}, {{1,1},{1,0},{1,0}}, {{1,1,1},{0,0,1}},
								  {{1,0},{1,1},{0,1}}, {{0,1,1},{1,1,0}}, {{0,1},{1,1},{1,0}}, {{1,1,0},{0,1,1}}};
	
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		map = new int[N][M];

		for (int i = 0; i < N; ++i) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; ++j) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		getAnswer();
		
		bw.write(answer + "\n");
		bw.flush();bw.close();br.close();
	}
	
	public static void getAnswer() {
		for (int k = 0; k < tetromino.length; ++k) {
			//k번째 테트로미노의 가로, 세로 길이
			int y = tetromino[k].length;
			int x = tetromino[k][0].length;
			
			for (int i = 0; i < N; ++i) {
				for (int j = 0; j < M; ++j) {
					int sum = 0;
					
					//범위를 벗어나지 않는다면
					if (i + y <= N && j + x <= M) {
						for (int t = 0; t < y; ++t) {
							for (int h = 0; h < x; ++h) {
								//테트로미노가 있는 부분의 종이값을 누적
								if (tetromino[k][t][h] == 1) {
									sum += map[i + t][j + h];
								}
							}
						}
					}
					answer = Math.max(answer, sum);
				}
			}
		}
	}
}