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) {
}
;
}
}
'Algorithm > 문제' 카테고리의 다른 글
[백준 / JAVA] 17140. 이차원 배열과 연산 (G4) (0) | 2024.04.12 |
---|---|
[백준 / JAVA] 14502. 연구소 (G4) (0) | 2024.04.12 |
[백준 / JAVA] 14499. 주사위 굴리기 (G4) (1) | 2024.04.11 |
[백준 / JAVA] 21610. 마법사 상어와 비바라기 (G5) (0) | 2024.04.10 |
[백준 / JAVA] 21608. 상어 초등학교 (G5) (0) | 2024.04.10 |