[Java/BruteForce] 백준 2116. 주사위쌓기

🤔 Intuition

// 맨 아래의 어떤 숫자를 고르고 그 숫자에 따라 연쇄적으로 나머지 주사위들의 숫자를 지운 뒤 최대값의 합을 출력
// 시간제한이 최대 2초이므로 완탐을 노리고 있는 것으로 보인다.

🔎 Algorithm & Complexity

* @algorithm brute-force
* @time O(D^2 * N) : 처음 주사위의 윗면 고르기 D * N개의 주사위 순회 * 각 주사위 정해진 윗면 찾기 D -> 428 ms
* @memory O(N*D) : N개의 주사위 면 정보 저장 배열 -> 41928 KB

* D : 주사위 면 개수(=6), N : 주사위 개수

👨🏻‍💻 Logic

// 주사위들을 배열로 저장해둔다.
// 첫 번째 주사위의 선택 숫자를 6으로 순회한다. (이는 윗 면을 어떤 걸로 할지를 선택하는 거라서 6까지 순회해야 함
// 맨 아래 선택된 주사위에 따라 나머지 주사위의 숫자는 모두 정해짐, 남은 순자중 최대값을 탐색

 

public class BOJ_2116_주사위쌓기 {
    private static int ans;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int[][] dices = new int[N][6];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 6; j++) {
                dices[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < 6; i++) {
            int res = 0;
            int upperPlane = dices[0][i];
            int oppositePlane = dices[0][getOppositePlane(i)];
            res += Arrays.stream(dices[0])
                    .filter(o -> o != upperPlane && o != oppositePlane)
                    .max()
                    .getAsInt();
            int stdPlane = upperPlane;
            for (int j = 1; j < N; j++) {
                int idx = 0;
                for (int k = 0; k < 6; k++) {
                    if (dices[j][k] == stdPlane) {
                        idx = k;
                        break;
                    }
                }
                int uPlane = dices[j][idx];
                int oPlane = dices[j][getOppositePlane(idx)];
                res += Arrays.stream(dices[j])
                        .filter(o -> o != uPlane && o != oPlane)
                        .max()
                        .getAsInt();
                stdPlane = oPlane;
            }
            ans = Math.max(ans, res);
        }

        br.close();
        bw.write(sb.append(ans).toString());
        bw.flush();
        bw.close();
    }

    private static int getOppositePlane(int i) {
        if (i == 0 || i == 5) {
            return i == 0 ? 5 : 0;
        } else if (i == 1 || i == 3) {
            return i == 1 ? 3 : 1;
        } else if (i == 2 || i == 4) {
            return i == 2 ? 4 : 2;
        }
        return -1;
    }
}

 

🔥 Other's Idea

다른 이는 메모리 19760 KB , 시간 176 ms 정도로 풀이를 해냈길래 이를 읽어봤다.

케이스를 나눠서 DP 타뷸레이션을 통해 풀어낸 로직이었다.

 

생각을 안해본건 아니였으나 의도가 완탐이라 생각해서 굳이 짜려는 시도를 하지 않았는데, 효율성의 차이를 보니 조금 아쉬움이 느껴진다.

 

구성된 논리는, 2차원 dp 배열을 저장하여 각 경우에서 숫자의 최대값을 케이스를 구분하여 저장해두고 이를 차곡차곡 쌓아가는 원리이다.

public class Main {
	static int N;
	static int [][]dp;
	public static void main(String[] args) throws Exception{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));	
		StringTokenizer st;
		N=Integer.parseInt(br.readLine());
		dp=new int[N][6];
		
		int []prev_dice=new int[6];
		
		for(int i=0;i<N;i++) {
			st=new StringTokenizer(br.readLine());
			int[] dice=new int[6];
			
			for(int j=0;j<6;j++) {
				dice[j]=Integer.parseInt(st.nextToken());
			}
			
			//1~4
			dp[i][0]=dp[i][5]=Math.max(dice[1], Math.max(dice[2], Math.max(dice[3], dice[4])));
			
			//0135
			dp[i][2]=dp[i][4]=Math.max(dice[0], Math.max(dice[1], Math.max(dice[3], dice[5])));
			
			//0245
			dp[i][1]=dp[i][3]=Math.max(dice[0], Math.max(dice[2], Math.max(dice[4], dice[5])));
			
			if(i!=0) {
				for(int a=0;a<6;a++) { //dice
					for(int b=0;b<6;b++) { //prev_dice
						if(dice[a]==prev_dice[b]) {
							if(b==0) {
								dp[i][a]+=dp[i-1][5];
							}
							else if(b==1){
								dp[i][a]+=dp[i-1][3];
							}
							else if(b==2){
								dp[i][a]+=dp[i-1][4];
							}
							else if(b==3){
								dp[i][a]+=dp[i-1][1];
							}
							else if(b==4){
								dp[i][a]+=dp[i-1][2];
							}
							else {
								dp[i][a]+=dp[i-1][0];
							}
							break;
						}
					}
				}
			}
			
			prev_dice=dice;
		}
		
		int result=0;
		for(int i=0;i<6;i++) {
			result=Math.max(result, dp[N-1][i]);
		}
		
		System.out.println(result);
	}	
}