알고리즘/BOJ
[ 백준 14500 테트로미노 ] 문제 풀이(Java) - 삼성 SW역량테스트 기출
myeongmy
2020. 4. 16. 18:58
반응형
어렵진 않은 문제이나 실수하기 좋은 시뮬레이션 문제입니다! 틀리면 디버깅하기도 어렵,,,,
문제보기
https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누
www.acmicpc.net
나의 풀이
테트로미노 블록을 올려놓았을 때 점수가 최대가 되는 때를 구하는 문제입니다. 그러므로 블록을 올릴 수 있는 모든 경우의 수, 가능한 모든 블록의 모양을 다 탐색해주는 브루트 포스 문제입니다.
문제에 제시된 테트로미노 모형은 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();
}
}
}
결과
반응형