99클럽 코테 스터디 25일차 TIL 완전탐색(주사위 쌓기)

https://www.acmicpc.net/problem/2116

 

<아이디어>

이 문제는 처음에 아이디어 설계하는 게 젤 힘들었다.

이렇게 하는 게 맞나..? 하면서 풀긴 했는데 주사위 개수 범위가 작아서 완탐으로 가능했던 것 같다.

아이디어를 정리해보면

1. 1번 주사위의 모든 면을 바닥으로 두고 각각의 경우를 계산 시작한다.

2. 0-5, 1-3, 2-4 면이 각각 마주보는 면이라는 것을 이용하여 현재 바닥의 윗면을 찾는다.

3. 이렇게 찾은 바닥과 윗면을 제외한 모든 수를 열의 크기가 4인 map 배열에 넣어준다.

4. 이때, 현재 윗면이 다음 주사위의 바닥이 될 것이므로, 다음 주사위의 바닥을 새롭게 찾아주어야 한다(nBottom)

5. 이런식으로 계속 바닥면과 윗면을 찾아서 각각의 옆면이 될 수 있는 모든 수를 map에 넣어주고, map 배열을 내림차순 정렬한다.

6. 정렬한 맨 앞 값만 더했을 때가 가장 최댓값일 것이므로 sum으로 계산하고, ans에 갱신을 통해 가장 큰 sum을 찾아 출력한다.

 

<제출코드>

package Study.Week04;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Day25_BOJ_2116_주사위쌓기 {

    static int n;
    static int ans;
    static int[][] arr;
    static Integer[][] map;

    public static void isBottom(int bottom){
        int top = 0;
        map = new Integer[n][4];
        for(int i=0; i<n; i++){
            // 이번 top 찾기
            for(int j=0; j<6; j++){
                if(arr[i][j] == bottom && j == 0) top = arr[i][5];
                else if(arr[i][j] == bottom && j == 1) top = arr[i][3];
                else if(arr[i][j] == bottom && j == 2) top = arr[i][4];
                else if(arr[i][j] == bottom && j == 3) top = arr[i][1];
                else if(arr[i][j] == bottom && j == 4) top = arr[i][2];
                else if(arr[i][j] == bottom && j == 5) top = arr[i][0];
            }
            int idx = 0;
            int nBottom = 0;
            for(int j=0; j<6; j++){
                if(arr[i][j] == bottom) continue;
                if(arr[i][j] == top) {
                    nBottom = top;       // 다음 bottom
                    continue;
                }
                map[i][idx++] = arr[i][j];
            }
            // 다음 bottom 바통터치
            bottom = nBottom;
        }
        // 이 경우 옆면의 최댓값 계산
        for(int i=0; i<n; i++){
            Arrays.sort(map[i], Collections.reverseOrder());
        }
        int sum = 0;
        for(int i=0; i<n; i++){
            sum += map[i][0];
        }
        ans = Math.max(ans, sum);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        arr = new int[n][6];
        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<6; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        // 1번 주사위의 모든 경우의 수
        for(int i=0; i<6; i++){
            isBottom(arr[0][i]);
        }
        System.out.println(ans);
    }
}