본문 바로가기

Algorithm/문제

[백준 / JAVA] 14500. 테트로미노 (G4)

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

 

14500번: 테트로미노

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변

www.acmicpc.net

 

 

요령이 없는 문제지만 나름 요령있게 풀었다. 일자와 네모는 각각 구현해야 하지만 L자, 제트, ^오^는 한번에 계산할 수 있다. 머리를 굴리면 2x3칸의 직사각형에서 2칸씩 제거하는 방식으로 저 세 가지 도형의 돌리고 뒤집은 형태를 모두 만들 수 있다. 우리가 필요한 건 최대값이니 6칸을 모두 더한 후 선택한 2칸들 중 합이 가장 작은 값을 빼면 된다!

 

라고 가정했는데 실패했으면 너무 슬펐을 것 같다.

 

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

public class Main {
	static BufferedReader br;
	static StringTokenizer st;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
		sb = new StringBuilder();
		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());
		}
		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++) {
				I(i, j);
				square(i, j);
				LZO(i, j);
			}
		System.out.println(max);
	}

	static int N, M, map[][], max = -1;

	static void LZO(int row, int col) { // 꺾쇠, 제트, ㅗ 모두 6칸 직사각형에서 빼서 구현 가능
		try { // 가로
			int total = 0; // 2*3 칸 값 더함
			total += map[row][col];
			total += map[row][col + 1];
			total += map[row][col + 2];
			total += map[row + 1][col];
			total += map[row + 1][col + 1];
			total += map[row + 1][col + 2];
			int min = 3000;
			// 꺽쇠 처리
			min = Math.min(map[row][col] + map[row][col + 1], min);
			min = Math.min(map[row][col + 1] + map[row][col + 2], min);
			min = Math.min(map[row + 1][col] + map[row + 1][col + 1], min);
			min = Math.min(map[row + 1][col + 1] + map[row + 1][col + 2], min);
			// 제트 처리
			min = Math.min(map[row][col] + map[row + 1][col + 2], min);
			min = Math.min(map[row][col + 2] + map[row + 1][col], min);
			// ㅗ 처리
			min = Math.min(map[row][col] + map[row][col + 2], min);
			min = Math.min(map[row + 1][col] + map[row + 1][col + 2], min);
			max = Math.max(total - min, max);
		} catch (Exception e) {
		}
		;
		try { // 세로
			int total = 0; // 3*2 칸 값 더함
			total += map[row][col];
			total += map[row + 1][col];
			total += map[row + 2][col];
			total += map[row][col + 1];
			total += map[row + 1][col + 1];
			total += map[row + 2][col + 1];
			int min = 3000;
			// 꺽쇠 처리
			min = Math.min(map[row][col] + map[row + 1][col], min);
			min = Math.min(map[row][col + 1] + map[row + 1][col + 1], min);
			min = Math.min(map[row + 1][col] + map[row + 2][col], min);
			min = Math.min(map[row + 1][col + 1] + map[row + 2][col + 1], min);
			// 제트 처리
			min = Math.min(map[row][col] + map[row + 2][col + 1], min);
			min = Math.min(map[row][col + 1] + map[row + 2][col], min);
			// ㅗ 처리
			min = Math.min(map[row][col + 1] + map[row + 2][col + 1], min);
			min = Math.min(map[row][col] + map[row + 2][col], min);
			max = Math.max(total - min, max);
		} catch (Exception e) {
		}
		;
	}

	static void square(int row, int col) { // 네모
		try {
			int tmp = 0;
			tmp += map[row][col];
			tmp += map[row][col + 1];
			tmp += map[row + 1][col];
			tmp += map[row + 1][col + 1];
			max = Math.max(tmp, max);
		} catch (Exception e) {
		}
		;
	}

	static void I(int row, int col) { // 일자
		try { // 가로
			int tmp = 0;
			tmp += map[row][col];
			tmp += map[row][col + 1];
			tmp += map[row][col + 2];
			tmp += map[row][col + 3];
			max = Math.max(tmp, max);
		} catch (Exception e) {
		}
		;
		try { // 세로
			int tmp = 0;
			tmp += map[row][col];
			tmp += map[row + 1][col];
			tmp += map[row + 2][col];
			tmp += map[row + 3][col];
			max = Math.max(tmp, max);
		} catch (Exception e) {
		}
		;
	}
}