문제 설명

문제 링크는 여기

14500번: 테트로미노

---

각 자리마다 값이 주어진 공간 N * M에서 테트로미노로 가릴 수 있는 최대 값을 구하면 된다. 테트로미노는 90도 회전, 좌우, 상하 반전이 가능하다.

접근

정말 무식한 방법으로 풀 수 있다. 다만 굉장히 귀찮을 뿐이다…

먼저 일단 N * M 공간에 대한 입력 값을 모두 저장했다.

StringTokenizer token = new StringTokenizer(br.readLine());
int N = Integer.parseInt(token.nextToken());
int M = Integer.parseInt(token.nextToken());
int[][] arr = new int[N][M];

for(int n=0; n<N; n++) {
	token = new StringTokenizer(br.readLine());
	for(int m=0; m<M; m++) {
		arr[n][m] = Integer.parseInt(token.nextToken());
	}
}

노가다의 시작 전 일단 최종 반환할 값인 result와 중간에 값 연산 시 변수로 사용할 temp를 선언하였다.

여기에서 나는 나름대로 연산량을 줄이기 위해 2*3 공간에 들어가지는 테트로미노에 대한 처리를 함께 수행하였다.

2*3 전체의 값을 더한 후, 각 도형에 맞게 빼야하는 값을 구한다. 이때 가장 적게 뺀 값이 가장 클 것이므로 뺄값의 최소값을 찾아 최종적으로 temp에서 해당 값을 뺐다. 이후 result와 해당 값을 비교하여 더 큰 값으로 update 하였다.

int result = 0;
int temp;

각 도형의 회전, 반전에 대한 모든 값의 경우의 수를 구한다.

// 2*2 네모
for(int n=0; n<N-1; n++) {
	for(int m=0; m<M-1; m++) {
		temp = arr[n][m]+arr[n+1][m]+arr[n+1][m+1]+arr[n][m+1];
		result = Math.max(temp, result);
	}
}

// 1*4 막대
for(int n=0; n<N-3; n++) {
	for(int m=0; m<M; m++) {
		temp = arr[n][m]+arr[n+1][m]+arr[n+2][m]+arr[n+3][m];
		result = Math.max(temp, result);
	}
}

// 4*1 막대
for(int n=0; n<N; n++) {
	for(int m=0; m<M-3; m++) {
		temp = arr[n][m]+arr[n][m+1]+arr[n][m+2]+arr[n][m+3];
		result = Math.max(temp, result);
	}
}

// 2*3 도형들
for(int n=0; n<N-1; n++) {
	for(int m=0; m<M-2; m++) {
		temp = arr[n][m]+arr[n][m+1]+arr[n][m+2]
				+arr[n+1][m]+arr[n+1][m+1]+arr[n+1][m+2];
		
		// L 모양
		int temp2 = Math.min(arr[n][m]+arr[n][m+1], arr[n][m+1]+arr[n][m+2]);
		temp2 = Math.min(temp2, arr[n+1][m]+arr[n+1][m+1]);
		temp2 = Math.min(temp2, arr[n+1][m+1]+arr[n+1][m+2]);
		
		// Z 모양
		temp2 = Math.min(temp2, arr[n][m]+arr[n+1][m+2]);
		temp2 = Math.min(temp2, arr[n+1][m]+arr[n][m+2]);
		
		// T 모양
		temp2 = Math.min(temp2, arr[n][m]+arr[n][m+2]);
		temp2 = Math.min(temp2, arr[n+1][m]+arr[n+1][m+2]);
		
		result = Math.max(temp - temp2, result);
	}
}

// 3*2 도형들
for(int n=0; n<N-2; n++) {
	for(int m=0; m<M-1; m++) {
		temp = arr[n][m]+arr[n][m+1]
				+arr[n+1][m]+arr[n+1][m+1]
				+arr[n+2][m]+arr[n+2][m+1];
		
		// L 모양
		int temp2 = Math.min(arr[n][m]+arr[n+1][m], arr[n+1][m]+arr[n+2][m]);
		temp2 = Math.min(temp2, arr[n][m+1]+arr[n+1][m+1]);
		temp2 = Math.min(temp2, arr[n+1][m+1]+arr[n+2][m+1]);
		
		// Z 모양
		temp2 = Math.min(temp2, arr[n][m]+arr[n+2][m+1]);
		temp2 = Math.min(temp2, arr[n][m+1]+arr[n+2][m]);
		
		// T 모양
		temp2 = Math.min(temp2, arr[n][m]+arr[n+2][m]);
		temp2 = Math.min(temp2, arr[n][m+1]+arr[n+2][m+1]);
		
		result = Math.max(temp - temp2, result);
	}
}
System.out.println(result);

소스코드

최종적으로 제출한 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer token = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(token.nextToken());
		int M = Integer.parseInt(token.nextToken());
		int[][] arr = new int[N][M];
		
		for(int n=0; n<N; n++) {
			token = new StringTokenizer(br.readLine());
			for(int m=0; m<M; m++) {
				arr[n][m] = Integer.parseInt(token.nextToken());
			}
		}
		int result = 0;
		int temp;
		
		// 2*2 네모
		for(int n=0; n<N-1; n++) {
			for(int m=0; m<M-1; m++) {
				temp = arr[n][m]+arr[n+1][m]+arr[n+1][m+1]+arr[n][m+1];
				result = Math.max(temp, result);
			}
		}
		
		// 1*4 막대
		for(int n=0; n<N-3; n++) {
			for(int m=0; m<M; m++) {
				temp = arr[n][m]+arr[n+1][m]+arr[n+2][m]+arr[n+3][m];
				result = Math.max(temp, result);
			}
		}
		
		// 4*1 막대
		for(int n=0; n<N; n++) {
			for(int m=0; m<M-3; m++) {
				temp = arr[n][m]+arr[n][m+1]+arr[n][m+2]+arr[n][m+3];
				result = Math.max(temp, result);
			}
		}
		
		// 2*3 도형들
		for(int n=0; n<N-1; n++) {
			for(int m=0; m<M-2; m++) {
				temp = arr[n][m]+arr[n][m+1]+arr[n][m+2]
						+arr[n+1][m]+arr[n+1][m+1]+arr[n+1][m+2];
				
				// L 모양
				int temp2 = Math.min(arr[n][m]+arr[n][m+1], arr[n][m+1]+arr[n][m+2]);
				temp2 = Math.min(temp2, arr[n+1][m]+arr[n+1][m+1]);
				temp2 = Math.min(temp2, arr[n+1][m+1]+arr[n+1][m+2]);
				
				// Z 모양
				temp2 = Math.min(temp2, arr[n][m]+arr[n+1][m+2]);
				temp2 = Math.min(temp2, arr[n+1][m]+arr[n][m+2]);
				
				// T 모양
				temp2 = Math.min(temp2, arr[n][m]+arr[n][m+2]);
				temp2 = Math.min(temp2, arr[n+1][m]+arr[n+1][m+2]);
				
				result = Math.max(temp - temp2, result);
			}
		}
		
		// 3*2 도형들
		for(int n=0; n<N-2; n++) {
			for(int m=0; m<M-1; m++) {
				temp = arr[n][m]+arr[n][m+1]
						+arr[n+1][m]+arr[n+1][m+1]
						+arr[n+2][m]+arr[n+2][m+1];
				
				// L 모양
				int temp2 = Math.min(arr[n][m]+arr[n+1][m], arr[n+1][m]+arr[n+2][m]);
				temp2 = Math.min(temp2, arr[n][m+1]+arr[n+1][m+1]);
				temp2 = Math.min(temp2, arr[n+1][m+1]+arr[n+2][m+1]);
				
				// Z 모양
				temp2 = Math.min(temp2, arr[n][m]+arr[n+2][m+1]);
				temp2 = Math.min(temp2, arr[n][m+1]+arr[n+2][m]);
				
				// T 모양
				temp2 = Math.min(temp2, arr[n][m]+arr[n+2][m]);
				temp2 = Math.min(temp2, arr[n][m+1]+arr[n+2][m+1]);
				
				result = Math.max(temp - temp2, result);
			}
		}
		
		System.out.println(result);
	}
}

결과

제출결과는 다음과 같다.

과거 파이썬 제출기록보다 빠르길래 비교해보니까 이전엔 각 도형마다 일일히 반복문을 사용했었다. 역시 2*3크기의 테트로미노에 대한 처리를 한꺼번에 안해준 것이 시간복잡도 개선에 기여해준 것 같았다.

고찰

이런 문제도 규칙을 찾아서 해결할 수 있나? 흠.. 단순 구현 문제로 보이면 일단 지금처럼 먼저 무지성 구현해보는 것도 나쁘지는 않은 것 같다.