[BOJ] 14500 테트로미노 - Java

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

14500번: 테트로미노

---

1. 문제

NxM 크기의 map에서 다음과 같은 5종류의 테트로미노를 적절히 놓았을 때 놓인 칸에 쓰여 있는 수들의 합이 최대가 될 때의 합을 출력한다.

2. 풀이

이 문제는 정확성을 요구한다. 모든 경우의 수를 다 찾아서 배열을 만들어야 한다.

경우의 수 하나라도 빠지면 바로 오답 처리가 된다.

3. 코드

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

public class Main {
    
	static int N, M, max, map[][];
	
	static int[][] dy = {
			{0,0,0,0},
			{0,1,2,3},
			
			{0,0,1,1},
			
			{0,0,0,-1},
			{0,0,0,1},
			{0,1,2,2},
			{0,1,2,2},
			
			{0,1,1,1},
			{0,0,1,2},
			{0,0,0,1},
			{0,0,1,2},
			
			{0,1,1,2},
			{0,1,1,2},
			{0,0,1,1},
			{0,0,-1,-1},
			
			{0,-1,-1,-1},
			{0,-1,0,1},
			{0,1,1,1},
			{0,-1,0,1}
	};
	static int[][] dx = {
			{0,1,2,3},
			{0,0,0,0},
			
			{0,1,0,1},
			
			{0,1,2,2},
			{0,1,2,2},
			{0,0,0,-1},
			{0,0,0,1},
			
			{0,0,1,2},
			{0,1,1,1},
			{0,-1,-2,-2},
			{0,-1,-1,-1},
			
			{0,0,-1,-1},
			{0,0,1,1},
			{0,1,1,2},
			{0,1,1,2},
			
			{0,-1,0,1},
			{0,1,1,1},
			{0,-1,0,1},
			{0,-1,-1,-1}
	};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer 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());
			}
		}
		// 입력 끝
		
		int len = dy.length;
		max = Integer.MIN_VALUE;
		for (int y=0; y<N; y++) {
			for (int x=0; x<M; x++) {
				for (int i=0; i<len; i++) {
					int sum = 0;
					for (int d=0; d<4; d++) {
						int ny = y+dy[i][d];
						int nx = x+dx[i][d];
						if (ny<0 || ny>=N || nx<0 || nx>=M) continue;
						sum += map[ny][nx];
					}
					max = Math.max(max, sum);
				}
			}
		}
		System.out.println(max);
	}
}

4. 사담

재밌었다. 빡구현 문제치곤 로직이 복잡한 것은 아니었으나 모든 경우의 수를 빠짐없이 찾아야 하는 노가다성 문제였다.

이틀 걸렸지만 재밌었다..