boj)14500 - 테트로미노
2020. 9. 22. 12:00ㆍPS/boj
import java.io.*;
import java.util.StringTokenizer;
public class boj_14500 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int[][] a;
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
a = new int[n][m];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
a[i][j] = Integer.parseInt(st.nextToken());
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (j+3 < m) {
int temp = a[i][j] + a[i][j+1] + a[i][j+2] + a[i][j+3];
if (ans < temp) ans = temp;
}
if (i+3 < n) {
int temp = a[i][j] + a[i+1][j] + a[i+2][j] + a[i+3][j];
if (ans < temp) ans = temp;
}
if (i+1 < n && j+2 < m) {
int temp = a[i][j] + a[i+1][j] + a[i+1][j+1] + a[i+1][j+2];
if (ans < temp) ans = temp;
}
if (i+2 < n && j+1 < m) {
int temp = a[i][j] + a[i][j+1] + a[i+1][j] + a[i+2][j];
if (ans < temp) ans = temp;
}
if (i+1 < n && j+2 < m) {
int temp = a[i][j] + a[i][j+1] + a[i][j+2] + a[i+1][j+2];
if (ans < temp) ans = temp;
}
if (i+2 < n && j-1 >= 0) {
int temp = a[i][j] + a[i+1][j] + a[i+2][j] + a[i+2][j-1];
if (ans < temp) ans = temp;
}
if (i-1 >= 0 && j+2 < m) {
int temp = a[i][j] + a[i][j+1] + a[i][j+2] + a[i-1][j+2];
if (ans < temp) ans = temp;
}
if (i+2 < n && j+1 < m) {
int temp = a[i][j] + a[i+1][j] + a[i+2][j] + a[i+2][j+1];
if (ans < temp) ans = temp;
}
if (i+1 < n && j+2 < m) {
int temp = a[i][j] + a[i][j+1] + a[i][j+2] + a[i+1][j];
if (ans < temp) ans = temp;
}
if (i+2 < n && j+1 < m) {
int temp = a[i][j] + a[i][j+1] + a[i+1][j+1] + a[i+2][j+1];
if (ans < temp) ans = temp;
}
if (i+1 < n && j+1 < m) {
int temp = a[i][j] + a[i][j+1] + a[i+1][j] + a[i+1][j+1];
if (ans < temp) ans = temp;
}
if (i-1 >= 0 && j+2 < m) {
int temp = a[i][j] + a[i][j+1] + a[i-1][j+1] + a[i-1][j+2];
if (ans < temp) ans = temp;
}
if (i+2 < n && j+1 < m) {
int temp = a[i][j] + a[i+1][j] + a[i+1][j+1] + a[i+2][j+1];
if (ans < temp) ans = temp;
}
if (i+1 < n && j+2 < m) {
int temp = a[i][j] + a[i][j+1] + a[i+1][j+1] + a[i+1][j+2];
if (ans < temp) ans = temp;
}
if (i+2 < n && j-1 >= 0) {
int temp = a[i][j] + a[i+1][j] + a[i+1][j-1] + a[i+2][j-1];
if (ans < temp) ans = temp;
}
if (j+2 < m) {
int temp = a[i][j] + a[i][j+1] + a[i][j+2];
if (i-1 >= 0) {
int temp2 = temp + a[i-1][j+1];
if (ans < temp2) ans = temp2;
}
if (i+1 < n) {
int temp2 = temp + a[i+1][j+1];
if (ans < temp2) ans = temp2;
}
}
if (i+2 < n) {
int temp = a[i][j] + a[i+1][j] + a[i+2][j];
if (j+1 < m) {
int temp2 = temp + a[i+1][j+1];
if (ans < temp2) ans = temp2;
}
if (j-1 >= 0) {
int temp2 = temp + a[i+1][j-1];
if (ans < temp2) ans = temp2;
}
}
}
}
System.out.println(ans);
}
}
생각
- 처음에는 그 행과 그 열에서 최대값을 체크한 뒤에 거기서 또 탐색해나가야 하나 ? 이런식으로 접근함
- 규칙을 못찾겠고 구현 못하겠어서 실패
- 조만간 머리가 터지지않을까
풀이과정
- 테트로미노로 만들어 질 수 있는 도형의 가짓수는 총 19개 (대칭, 회전)
- NM에 대하여 19번 반복해도 실행시간이 충분 -> 완전탐색으로
- 각 도형의 모양에 대해서 19번 전부 합을 구하고 그 중에 최댓값을 찾는 전략
- 19개의 도형의 모양을 생각하고 그 규칙에 맞게 합 구하기
'PS > boj' 카테고리의 다른 글
boj)1748 - 수 이어쓰기 1 (0) | 2020.09.22 |
---|---|
boj)6064 - 카잉 달력 (0) | 2020.09.22 |
boj)1107 - 리모컨 (0) | 2020.09.22 |
boj)1476 - 날짜 계산 (0) | 2020.09.21 |
boj)3085 - 사탕 게임 (0) | 2020.09.21 |