https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변
www.acmicpc.net
예전에 풀었던 기억이 있는 문제지만, 당시 나는 코테를 C++도 아닌 C로 봤던 사람이라 이 문제도 C로 풀었었다.
사실 문제에 있는 그림만 기억이 날 뿐 풀이 방식은 하나도 기억이 안 나서 JAVA로 다시 풀어봤다.
우선 골드4로 난이도가 정해져있긴 하지만, 풀고 난 뒤 드는 생각은 난이도 책정이 잘못되지 않았나 싶긴 했다.
N-Queen 문제는 알고리즘 분류를 안 보면 어떻게 풀지 감을 잡기가 어렵기라도 하지,이 문제는 사실 그냥 누가봐도
브루트포스 문제다. 그래서 한 지점을 기준으로 해당 위치에서 만들수 있는 모양마다 합연산 비교 후 최대값 출력하는 형식으로 했다.
참고로 아래 코드에서 주석으로 1번~19번은 모양 별 경우의 수를 나타내며, 그림에서 별 표시 기준점으로 삼을 위치를 표시했다.
import java.io.*;
import java.util.*;
public class boj14500 {
static int N, M, maxSum;
static int board[][];
public static void tetrio() {
int i, j;
for (i = 0; i < N; i++) {
for (j = 0; j < M; j++) {
if (isValid(i, 3, j, 0)) {// 1번
maxSum = Math.max(maxSum, board[i][j] + board[i + 1][j] + board[i + 2][j] + board[i + 3][j]);
}
if (isValid(i, 0, j, 3)) {// 2번
maxSum = Math.max(maxSum, board[i][j] + board[i][j + 1] + board[i][j + 2] + board[i][j + 3]);
}
if (isValid(i, 1, j, 1)) {// 3번
maxSum = Math.max(maxSum, board[i][j] + board[i + 1][j] + board[i + 1][j + 1] + board[i][j + 1]);
}
if (isValid(i, 2, j, 1)) {// 4번
maxSum = Math.max(maxSum, board[i][j] + board[i + 1][j] + board[i + 2][j] + board[i + 2][j + 1]);
}
if (isValid(i, 1, j, 2)) {// 5번
maxSum = Math.max(maxSum, board[i][j] + board[i + 1][j] + board[i][j + 1] + board[i][j + 2]);
}
if (isValid(i, 2, j, 1)) {// 6번
maxSum = Math.max(maxSum,
board[i][j] + board[i + 1][j + 1] + board[i + 2][j + 1] + board[i][j + 1]);
}
if (isValid(i, -1, j, 2)) {// 7번
maxSum = Math.max(maxSum, board[i][j] + board[i][j + 1] + board[i][j + 2] + board[i - 1][j + 2]);
}
if (isValid(i, 2, j, 1)) {// 8번
maxSum = Math.max(maxSum, board[i][j] + board[i + 1][j] + board[i + 2][j] + board[i][j + 1]);
}
if (isValid(i, -2, j, 1)) {// 9번
maxSum = Math.max(maxSum,
board[i][j] + board[i][j + 1] + board[i - 1][j + 1] + board[i - 2][j + 1]);
}
if (isValid(i, 1, j, 2)) {// 10번
maxSum = Math.max(maxSum,
board[i][j] + board[i + 1][j] + board[i + 1][j + 1] + board[i + 1][j + 2]);
}
if (isValid(i, 1, j, 2)) {// 11번
maxSum = Math.max(maxSum, board[i][j] + board[i][j + 1] + board[i][j + 2] + board[i + 1][j + 2]);
}
if (isValid(i, 2, j, 1)) {// 12번
maxSum = Math.max(maxSum,
board[i][j] + board[i + 1][j] + board[i + 1][j + 1] + board[i + 2][j + 1]);
}
if (isValid(i, 2, j, -1)) {// 13번
maxSum = Math.max(maxSum,
board[i][j] + board[i + 1][j] + board[i + 1][j - 1] + board[i + 2][j - 1]);
}
if (isValid(i, -1, j, 2)) {// 14번
maxSum = Math.max(maxSum,
board[i][j] + board[i][j + 1] + board[i - 1][j + 1] + board[i - 1][j + 2]);
}
if (isValid(i, 1, j, 2)) {// 15번
maxSum = Math.max(maxSum,
board[i][j] + board[i][j + 1] + board[i + 1][j + 1] + board[i + 1][j + 2]);
}
if (isValid(i, 1, j, 2)) {// 16 번
maxSum = Math.max(maxSum, board[i][j] + board[i][j + 1] + board[i + 1][j + 1] + board[i][j + 2]);
}
if (isValid(i, 2, j, -1)) {// 17 번
maxSum = Math.max(maxSum, board[i][j] + board[i + 1][j] + board[i + 2][j] + board[i + 1][j - 1]);
}
if (isValid(i, -1, j, 2)) {// 18 번
maxSum = Math.max(maxSum, board[i][j] + board[i][j + 1] + board[i - 1][j + 1] + board[i][j + 2]);
}
if (isValid(i, 2, j, 1)) {// 19 번
maxSum = Math.max(maxSum, board[i][j] + board[i + 1][j] + board[i + 2][j] + board[i + 1][j + 1]);
}
}
}
}
public static boolean isValid(int i, int plusI, int j, int plusJ) {
if (i + plusI >= N) {
return false;
}
if (i + plusI < 0) {
return false;
}
if (j + plusJ >= M) {
return false;
}
if (j + plusJ < 0) {
return false;
}
return true;
}
public static void pre() throws IOException {
int i, j;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
maxSum = 0;
board = new int[N][M];
for (i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (j = 0; j < M; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
}
public static void main(String[] args) throws IOException {
pre();
tetrio();
System.out.println(maxSum);
}
}
'알고리즘 > 알문풀(백준, 프로그래머스, 코드트리)' 카테고리의 다른 글
| [알고리즘] BOJ 18185 라면 사기(Small) (JAVA) (1) | 2023.10.11 |
|---|---|
| [알고리즘] BOJ 15486 퇴사 2 (JAVA) (0) | 2023.10.01 |
| [알고리즘] SWEA 1257 K번째 문자열 (JAVA) (0) | 2023.09.18 |
| [알고리즘] BOJ 2447 별 찍기-10 (JAVA) (0) | 2023.09.17 |
| [알고리즘] BOJ 1074 Z (JAVA) (0) | 2023.09.17 |
댓글