[ 백준 14500 테트로미노 ] 문제 풀이(Java) - 삼성 SW역량테스트 기출

 

어렵진 않은 문제이나 실수하기 좋은 시뮬레이션 문제입니다! 틀리면 디버깅하기도 어렵,,,,

 

 

문제보기

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

14500번: 테트로미노

 

나의 풀이

 

테트로미노 블록을 올려놓았을 때 점수가 최대가 되는 때를 구하는 문제입니다. 그러므로 블록을 올릴 수 있는 모든 경우의 수, 가능한 모든 블록의 모양을 다 탐색해주는 브루트 포스 문제입니다.

 

문제에 제시된 테트로미노 모형은 5개지만 회전, 대칭이 모두 가능하므로 가능한 총 블록의 수는 19개가 됩니다!

 

모든 블록 모양과 시작점

 

다음과 같이 19개의 블록을 N*M 종이 위에 모두 올려보면 됩니다. 블록을 올릴 때는 그 블록의 시작점이 올 수 있는 위치를 for문의 조건으로 선정하셔야 합니다!

 

 

코드

//브루트 포스 문제

import java.io.*;

public class N_14500 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			String[] arr = br.readLine().split(" ");
			int N = Integer.parseInt(arr[0]);
			int M = Integer.parseInt(arr[1]);

			int[][] A = new int[N][M];
			for (int i = 0; i < N; i++) {
				String[] arr1 = br.readLine().split(" ");
				for (int j = 0; j < M; j++) {
					A[i][j] = Integer.parseInt(arr1[j]);
				}
			}

			int max = Integer.MIN_VALUE;

			// 1번
			int sum = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j <= M - 4; j++) {
					sum = A[i][j] + A[i][j + 1] + A[i][j + 2] + A[i][j + 3];
					if (max < sum)
						max = sum;
				}
			}

			// 2번
			for (int i = 0; i <= N - 4; i++) {
				for (int j = 0; j < M; j++) {
					sum = A[i][j] + A[i + 1][j] + A[i + 2][j] + A[i + 3][j];
					if (max < sum)
						max = sum;
				}
			}

			// 3번
			for (int i = 0; i <= N - 2; i++) {
				for (int j = 0; j <= M - 2; j++) {
					sum = A[i][j] + A[i + 1][j] + A[i][j + 1] + A[i + 1][j + 1];
					if (max < sum)
						max = sum;
				}
			}

			// 4번
			for (int i = 0; i <= N - 3; i++) {
				for (int j = 0; j <= M - 2; j++) {
					sum = A[i][j] + A[i + 1][j] + A[i + 2][j] + A[i + 2][j + 1];
					if (max < sum)
						max = sum;
				}
			}

			// 5번
			for (int i = 0; i <= N - 2; i++) {
				for (int j = 2; j < M; j++) {
					sum = A[i][j] + A[i][j - 1] + A[i][j - 2] + A[i + 1][j - 2];
					if (max < sum)
						max = sum;
				}
			}

			// 6번
			for (int i = 0; i <= N - 3; i++) {
				for (int j = 0; j <= M - 2; j++) {
					sum = A[i][j] + A[i][j + 1] + A[i + 1][j + 1] + A[i + 2][j + 1];
					if (max < sum)
						max = sum;
				}
			}

			// 7번
			for (int i = 0; i <= N - 2; i++) {
				for (int j = 2; j < M; j++) {
					sum = A[i][j] + A[i + 1][j] + A[i + 1][j - 1] + A[i + 1][j - 2];
					if (max < sum)
						max = sum;
				}
			}

			// 8번
			for (int i = 0; i <= N - 3; i++) {
				for (int j = 1; j < M; j++) {
					sum = A[i][j] + A[i + 1][j] + A[i + 2][j] + A[i + 2][j - 1];
					if (max < sum)
						max = sum;
				}
			}

			// 9번
			for (int i = 0; i <= N - 2; i++) {
				for (int j = 0; j <= M - 3; j++) {
					sum = A[i][j] + A[i + 1][j] + A[i + 1][j + 1] + A[i + 1][j + 2];
					if (max < sum)
						max = sum;
				}
			}

			// 10번
			for (int i = 0; i <= N - 3; i++) {
				for (int j = 1; j < M; j++) {
					sum = A[i][j] + A[i][j - 1] + A[i + 1][j - 1] + A[i + 2][j - 1];
					if (max < sum)
						max = sum;
				}
			}

			// 11번
			for (int i = 0; i <= N - 2; i++) {
				for (int j = 0; j <= M - 3; j++) {
					sum = A[i][j] + A[i][j + 1] + A[i][j + 2] + A[i + 1][j + 2];
					if (max < sum)
						max = sum;
				}
			}

			// 12번
			for (int i = 0; i <= N - 3; i++) {
				for (int j = 0; j <= M - 2; j++) {
					sum = A[i][j] + A[i + 1][j] + A[i + 1][j + 1] + A[i + 2][j + 1];
					if (max < sum)
						max = sum;
				}
			}

			// 13번
			for (int i = 0; i <= N - 2; i++) {
				for (int j = 2; j < M; j++) {
					sum = A[i][j] + A[i][j - 1] + A[i + 1][j - 1] + A[i + 1][j - 2];
					if (max < sum)
						max = sum;
				}
			}

			// 14번
			for (int i = 0; i <= N - 3; i++) {
				for (int j = 1; j < M; j++) {
					sum = A[i][j] + A[i + 1][j] + A[i + 1][j - 1] + A[i + 2][j - 1];
					if (max < sum)
						max = sum;
				}
			}

			// 15번
			for (int i = 0; i <= N - 2; i++) {
				for (int j = 0; j <= M - 3; j++) {
					sum = A[i][j] + A[i][j + 1] + A[i + 1][j + 1] + A[i + 1][j + 2];
					if (max < sum)
						max = sum;
				}
			}

			// 16번
			for (int i = 0; i <= N - 2; i++) {
				for (int j = 0; j <= M - 3; j++) {
					sum = A[i][j] + A[i][j + 1] + A[i][j + 2] + A[i + 1][j + 1];
					if (max < sum)
						max = sum;
				}
			}

			// 17번
			for (int i = 0; i <= N - 3; i++) {
				for (int j = 1; j < M; j++) {
					sum = A[i][j] + A[i + 1][j] + A[i + 1][j - 1] + A[i + 2][j];
					if (max < sum)
						max = sum;
				}
			}

			// 18번
			for (int i = 0; i <= N - 2; i++) {
				for (int j = 1; j <= M - 2; j++) {
					sum = A[i][j] + A[i + 1][j - 1] + A[i + 1][j] + A[i + 1][j + 1];
					if (max < sum)
						max = sum;
				}
			}

			// 19번
			for (int i = 0; i <= N - 3; i++) {
				for (int j = 0; j <= M - 2; j++) {
					sum = A[i][j] + A[i + 1][j] + A[i + 1][j + 1] + A[i + 2][j];
					if (max < sum)
						max = sum;
				}
			}
			
			System.out.println(max);
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

}

 

결과

채점 결과