[백준]14500 번 - 테트로미노 <브루트포스>

 

 문제접근 

 

문제에서 제시된 모양으로 나올 수 있는 경우의 수는 위가 전부이다.

내가 문제 해결을 위해 생각한 방법은 6칸의 사각형 가로, 세로 모양과 막대, 사각형 이 4가지의 경우로 좁힌것이다.

표현해 보면

위 4가지에 대해서만 생각했다.

정사각형 모양과 막대 모양은 원래의 테트로미노에 대해 고려한 것이고, 나머지 3개의 테트로미노에 대해서는

위의 초록색 사각형 2개의 모양에서 2개 만큼의 값을 뺀 것 중 최댓값을 구하려 했다.

 

---

 풀이 - 정사각형 

public static int calculate_caseRectangular4(int[][] arr_NM, int max) {
    int cal_val=0;
    for(int i=0;i<arr_NM.length-1;i++) {
        for(int j=0;j<arr_NM[0].length-1;j++) {
            cal_val = arr_NM[i][j] + arr_NM[i][j+1] + arr_NM[i+1][j+1] + arr_NM[i+1][j];
            max = cal_val>max ? cal_val : max;

        }
    }
    return max;
}

정사각형의 경우 회전, 대칭을 해도 모양이 같기 때문에 주어진 N x M 배열을 모두 한번씩 돌도록 만들었다.

매 반복마다 cal_val이란 변수에 값을 계산하고 기존의 최댓값인 max 보다 크다면 max 값을 새로 갱신해준다.

 

---

 풀이 - 막대 모양 

public static int calculate_caseStraight4(int[][] arr_NM, int max) {
    int cal_val = 0;
    for(int i=0;i<arr_NM.length;i++) {
        for(int j=0;j<arr_NM[0].length-3;j++) {
            cal_val = arr_NM[i][j] + arr_NM[i][j+1] + arr_NM[i][j+2] + arr_NM[i][j+3];
            max = cal_val>max ? cal_val : max;
        }
    }

    for(int j=0;j<arr_NM[0].length;j++) {
        for(int i=0;i<arr_NM.length-3;i++) {
            cal_val = arr_NM[i][j] + arr_NM[i+1][j] + arr_NM[i+2][j] + arr_NM[i+3][j];
            max = cal_val>max ? cal_val : max;
        }
    }

    return max;
}

막대 모양의 경우, 누워있는 경우와 서있는 경우 2가지를 각각 계산하였다.

기준이 되는 i,j의 좌표는 막대 모양 가장 좌측, 상측의 좌표를 기준으로 하였다.

 

---

 풀이 - 6칸의 사각형 

public static int calculate_caseRectangular6U(int[][] arr_NM, int max) {
    int cal_val=0;
    int val_R3 = 0,val_L3 = 0,val_Rmax = 0,val_Lmax = 0, val_Pmin=0;
    for(int i=0;i<arr_NM.length-2;i++) {
        for(int j=0;j<arr_NM[0].length-1;j++) {
            val_L3 = arr_NM[i][j] + arr_NM[i+1][j] + arr_NM[i+2][j];
            val_R3 = arr_NM[i][j+1] + arr_NM[i+1][j+1] + arr_NM[i+2][j+1];
            val_Lmax = Math.max(arr_NM[i][j], Math.max(arr_NM[i+1][j], arr_NM[i+2][j]));
            val_Rmax = Math.max(arr_NM[i][j+1], Math.max(arr_NM[i+1][j+1], arr_NM[i+2][j+1]));
            val_Pmin = Math.min(arr_NM[i][j] + arr_NM[i+2][j+1], arr_NM[i][j+1] + arr_NM[i+2][j]);
            cal_val = max3(val_Rmax + val_L3, val_Lmax + val_R3, val_L3 + val_R3 - val_Pmin);
            max = max > cal_val ? max : cal_val;

        }
    }
    return max;
}
public static int calculate_caseRectangular6D(int[][] arr_NM, int max) {
    int cal_val=0;
    int val_U3 = 0,val_D3 = 0,val_Umax = 0,val_Dmax = 0, val_Pmin=0;
    for(int i=0;i<arr_NM.length-1;i++) {
        for(int j=0;j<arr_NM[0].length-2;j++) {
            val_D3 = arr_NM[i+1][j] + arr_NM[i+1][j+1] + arr_NM[i+1][j+2];
            val_U3 = arr_NM[i][j] + arr_NM[i][j+1] + arr_NM[i][j+2];
            val_Dmax = Math.max(arr_NM[i+1][j], Math.max(arr_NM[i+1][j+1], arr_NM[i+1][j+2]));
            val_Umax = Math.max(arr_NM[i][j], Math.max(arr_NM[i][j+1], arr_NM[i][j+2]));
            val_Pmin = Math.min(arr_NM[i][j] + arr_NM[i+1][j+2], arr_NM[i+1][j] + arr_NM[i][j+2]);
            cal_val = max3(val_Umax + val_D3, val_Dmax + val_U3, val_D3 + val_U3 - val_Pmin);
            max = max > cal_val ? max : cal_val;

        }
    }
    return max;
}

6칸의 경우 누워있는 경우와 서있는 경우(Down, Up)로 나누어 진행했다.

둘 다 6칸 중 최솟값 2칸을 뺀 값이 최댓값이 되므로 각 경우에 대해서 계산했다.

누워있는 경우로 예시를 들면 

1. 위칸 중 최댓값 + 아래 3칸의 합
2. 아래칸 중 최댓값 + 위 3칸의 합
3. 위 3칸의 합 + 아래 3칸의 합 - 사선의 최솟값

이 3가지 경우에 대해 계산했다. 3 케이스를 모두 구하고 가장 최댓값을 출력한다.

 

---

 코드 전문 

package Gold4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.stream.Stream;

public class num_145000 {

	public static void main(String[] args) throws IOException{
		/**
		 * 문제: 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.
		 * 			-> 정사각형은 서로 겹치면 안 된다.
		 * 			-> 도형은 모두 연결되어 있어야 한다.
		 * 			-> 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
		 * 		정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.
		 * 
		 * 		ㅁㅁㅁㅁ			ㅁㅁ
		 * 						    ㅁㅁ
		 * 		ㅁ		ㅁ
		 * 		ㅁ		ㅁㅁ		ㅁㅁㅁ
		 * 		ㅁㅁ		 ㅁ 		 ㅁ
		 * 
		 * 		아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.
		 * 		테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.
		 * 		테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.
		 * 
		 * 입력: 첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)
		 * 		둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 
		 * 		왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.
		 * 
		 * 출력: 첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.
		 * 
		 * 예제 
		 * 입력				출력		|		입력				출력		|	입력						출력
		 * 5 5      		19		|		4 5      		20      |	4 10               		7
		 * 1 2 3 4 5				|       1 2 3 4 5               |   1 2 1 2 1 2 1 2 1 2
		 * 5 4 3 2 1				|       1 2 3 4 5               |   2 1 2 1 2 1 2 1 2 1
		 * 2 3 4 5 6				|       1 2 3 4 5               |   1 2 1 2 1 2 1 2 1 2
		 * 6 5 4 3 2				|       1 2 3 4 5               |   2 1 2 1 2 1 2 1 2 1
		 * 1 2 1 2 1				|                               |
		 **/
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int[] val_NM = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		
		int[][] arr_NM = new int[val_NM[0]][val_NM[1]];
		
		for(int i=0;i<arr_NM.length;i++) arr_NM[i]= Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		
		System.out.println(caculate_Tetromino(arr_NM));
		
		
	}
	public static int caculate_Tetromino(int[][] arr_NM) {
		int max = 0;
		max = calculate_caseRectangular4(arr_NM, max);
		max = calculate_caseRectangular6D(arr_NM, max);
		max = calculate_caseRectangular6U(arr_NM, max);
		max = calculate_caseStraight4(arr_NM, max);
		return max;
	}
	public static int calculate_caseRectangular6U(int[][] arr_NM, int max) {
		int cal_val=0;
		int val_R3 = 0,val_L3 = 0,val_Rmax = 0,val_Lmax = 0, val_Pmin=0;
		for(int i=0;i<arr_NM.length-2;i++) {
			for(int j=0;j<arr_NM[0].length-1;j++) {
				val_L3 = arr_NM[i][j] + arr_NM[i+1][j] + arr_NM[i+2][j];
				val_R3 = arr_NM[i][j+1] + arr_NM[i+1][j+1] + arr_NM[i+2][j+1];
				val_Lmax = Math.max(arr_NM[i][j], Math.max(arr_NM[i+1][j], arr_NM[i+2][j]));
				val_Rmax = Math.max(arr_NM[i][j+1], Math.max(arr_NM[i+1][j+1], arr_NM[i+2][j+1]));
				val_Pmin = Math.min(arr_NM[i][j] + arr_NM[i+2][j+1], arr_NM[i][j+1] + arr_NM[i+2][j]);
				cal_val = max3(val_Rmax + val_L3, val_Lmax + val_R3, val_L3 + val_R3 - val_Pmin);
				max = max > cal_val ? max : cal_val;
				
			}
		}
		return max;
	}
	public static int calculate_caseRectangular6D(int[][] arr_NM, int max) {
		int cal_val=0;
		int val_U3 = 0,val_D3 = 0,val_Umax = 0,val_Dmax = 0, val_Pmin=0;
		for(int i=0;i<arr_NM.length-1;i++) {
			for(int j=0;j<arr_NM[0].length-2;j++) {
				val_D3 = arr_NM[i+1][j] + arr_NM[i+1][j+1] + arr_NM[i+1][j+2];
				val_U3 = arr_NM[i][j] + arr_NM[i][j+1] + arr_NM[i][j+2];
				val_Dmax = Math.max(arr_NM[i+1][j], Math.max(arr_NM[i+1][j+1], arr_NM[i+1][j+2]));
				val_Umax = Math.max(arr_NM[i][j], Math.max(arr_NM[i][j+1], arr_NM[i][j+2]));
				val_Pmin = Math.min(arr_NM[i][j] + arr_NM[i+1][j+2], arr_NM[i+1][j] + arr_NM[i][j+2]);
				cal_val = max3(val_Umax + val_D3, val_Dmax + val_U3, val_D3 + val_U3 - val_Pmin);
				max = max > cal_val ? max : cal_val;
				
			}
		}
		return max;
	}
	public static int calculate_caseRectangular4(int[][] arr_NM, int max) {
		int cal_val=0;
		for(int i=0;i<arr_NM.length-1;i++) {
			for(int j=0;j<arr_NM[0].length-1;j++) {
				cal_val = arr_NM[i][j] + arr_NM[i][j+1] + arr_NM[i+1][j+1] + arr_NM[i+1][j];
				max = cal_val>max ? cal_val : max;
				
			}
		}
		return max;
	}
	public static int calculate_caseStraight4(int[][] arr_NM, int max) {
		int cal_val = 0;
		for(int i=0;i<arr_NM.length;i++) {
			for(int j=0;j<arr_NM[0].length-3;j++) {
				cal_val = arr_NM[i][j] + arr_NM[i][j+1] + arr_NM[i][j+2] + arr_NM[i][j+3];
				max = cal_val>max ? cal_val : max;
			}
		}
		
		for(int j=0;j<arr_NM[0].length;j++) {
			for(int i=0;i<arr_NM.length-3;i++) {
				cal_val = arr_NM[i][j] + arr_NM[i+1][j] + arr_NM[i+2][j] + arr_NM[i+3][j];
				max = cal_val>max ? cal_val : max;
			}
		}
		
		return max;
	}
	public static int max3(int val1, int val2, int val3) {
		int max = 0;
		max = val1 > val2 ? val1 : val2;
		max = max > val3 ? max : val3;
		return max;
		
	}

}

N,M이 최대 500이고 4가지 경우 모두 돈다고 해도.. 1초가 안걸릴거라 생각했기 때문에 위 처럼 풀었다.

다른 사람들과 비교해도 효율은 나쁘지 않은듯함.