BOJ14500 테트로미노(Java)

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

태그 : 브루트포스

사고 흐름

풀이는 아마 대부분 문제 보자마자 떠오르는 것이 있을 것...

처음에 블럭 모양 다섯 개가 끝인 줄 알고 날먹하려다가,

회전 / 대칭이동이 가능하다는 것을 보고 뭔가 있나..하다가

그냥 배열 19개 만들고 브루트포스를 했다.

시간제한은 N <= 500에 O(N^2 x 19 x 3) 이면 2초는 넉넉하겠다고 생각했다.

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

public class Main {
	
	static BufferedReader br;
	static StringTokenizer st;
	static StringBuilder sb;
	static int n, m;
	static int arr[][];
	static int ans = 0;
	
	static int shapeR[][] = { { 0, 0, 0 }, { 1, 2, 3 }, { 1, 1, 0 }, { 1, 2, 2 }, {1, 2, 2 }, {0, 0, 1}, {0, 0, 1}, {0, 1, 2}, {0, 1, 2}, {0, 0, -1}, {1, 1, 1},  { 1, 1, 2 }, {1, 1, 2}, {0, -1, -1}, {0, 1, 1}, { 0, 0, 1 }, {-1, 0, 1}, {0, 0, -1}, {1, 1, 2} };
	static int shapeC[][] = { { 1, 2, 3 }, { 0, 0, 0 }, { 0, 1, 1 }, { 0, 0, 1 }, {0, 0, -1}, {1, 2, 0}, {1, 2, 2} , {1, 1, 1}, {1, 0, 0}, {1, 2, 2}, {0, 1, 2},  { 0, 1, 1 }, {0, -1, -1}, {1, 1, 2}, {1, 1, 2},  { 1, 2, 1 }, {1, 1, 1}, { 1, 2, 1}, {0, 1, 0} };
	
	static void solve() {
		for(int r = 0; r < n; ++r) {
			for(int c = 0; c < m; ++c) {
				for(int i = 0; i < 19; ++i) {
					boolean flag = true;
					int sum = arr[r][c];
					for(int j = 0; j < 3; ++j) {
						int checkR = r + shapeR[i][j];
						int checkC = c + shapeC[i][j];
						if (checkR >= n || checkR < 0 || checkC >= m || checkC < 0) {
							flag = false;
							break;
						}
						sum += arr[checkR][checkC];
					}
					if (flag) {
						ans = Math.max(ans, sum);
					}
				}
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		
		br = new BufferedReader(new InputStreamReader(System.in));
		sb = new StringBuilder();
		
		st = new StringTokenizer(br.readLine().trim());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		arr = new int[n][m];
		
		for (int i = 0; i < n; ++i) {
			st = new StringTokenizer(br.readLine().trim());
			for (int j = 0; j < m; ++j) {
				arr[i][j] = Integer.parseInt(st.nextToken()); 
			}
		}
		solve();
		
		System.out.println(ans);
	}

	
}

후기

ㅗ모양(...)을 제외한 블럭에 대한 모든 경우의 수를 깊이 3 이내의 dfs로 처리한다는 아이디어를 봤다.

전혀 떠올리지 못했는데 떠올린 사람들은 직관이 대단하다고 생각했다.

난 부끄럽지 않다