테트로미노 (14500)
1. 문제
2. 풀이
2-1. 조건
- 테트로미노를 회전, 대칭시킬 수 있다.
2-2. 풀이
회전과 대칭시켜서 만들 수 있는 모든 경우의 테트로미노를
놓을 수 있는 모든 위치에 두어보면 됩니다.
이런 문제는 보통 만들 수 있는 테트로미노를 테이블로 정의하고
반복문으로 모든 위치를 탐색한 다음 종이 위에 테트로미노를 올릴 때
아까 정의한 테이블을 이용합니다.
총 정리를 해보면
1. 회전과 대칭시켜서 만들 수 있는 모든 경우의 테트로미노를 테이블로 만듭니다.
2. 반복문으로 모든 위치를 탐색하며 테이블에 정의된 테트로미노를 올립니다.
3. 전체 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static int n, m, board[][];
static final int MIN = 0;
// 1.회전과 대칭시켜서 만들 수 있는 모든 경우의 테트로미노를 테이블로 만듭니다.
static int[][][] coverType = {
{{0,0},{0,1},{1,0},{1,1}},
{{0,0},{0,1},{0,2},{0,3}},
{{0,0},{1,0},{2,0},{3,0}},
{{0,0},{1,0},{2,0},{2,1}},
{{0,0},{0,1},{0,2},{1,0}},
{{0,0},{0,1},{1,1},{2,1}},
{{0,0},{0,1},{0,2},{-1,2}},
{{0,0},{0,1},{-1,1},{-2,1}},
{{0,0},{1,0},{1,1},{1,2}},
{{0,0},{0,1},{1,0},{2,0}},
{{0,0},{0,1},{0,2},{1,2}},
{{0,0},{1,0},{1,1},{2,1}},
{{0,0},{0,1},{-1,1},{-1,2}},
{{0,0},{1,0},{1,-1},{2,-1}},
{{0,0},{0,1},{1,1},{1,2}},
{{0,0},{1,-1},{1,0},{1,1}},
{{0,0},{1,0},{2,0},{1,1}},
{{0,0},{0,1},{0,2},{1,1}},
{{0,0},{1,0},{2,0},{1,-1}}
};
// 종이위에 테트로미노를 올리는 함수
static int cover(int type, int y, int x) {
int ret = 0;
for (int i = 0; i < 4; i++) {
int ny = y + coverType[type][i][0];
int nx = x + coverType[type][i][1];
if (ny < 0 || ny >= n || nx < 0 || nx >= m) return MIN;
ret += board[ny][nx];
}
return ret;
}
public static void main(String[] args) throws Exception {
String[] s = br.readLine().split(" ");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
board = new int[n][m];
for (int i = 0; i < n; i++) {
s = br.readLine().split(" ");
for (int j = 0; j < m; j++) {
board[i][j] = Integer.parseInt(s[j]);
}
}
int ans = MIN;
// 2. 반복문으로 모든 위치를 탐색하며 테이블에 정의된 테트로미노를 올립니다.
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int type = 0; type < 19; type++) {
ans = Math.max(ans, cover(type, i, j));
}
}
}
bw.write(ans + "");
bw.close();
}
}
Author And Source
이 문제에 관하여(테트로미노 (14500)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@front/백준-테트로미노-14500저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)