[TIL] 99클럽 코테 스터디 25일차 TIL + 백준 2116 주사위 쌓기

 

문제 풀이

 

문제 탐색하기

주사위를 쌓아올리는 데에는 아래 주사위의 윗면과 그 윗 주사위의 아랫면의 숫자가 같다는 규칙이 있습니다. 

첫번째 주사위의 윗면을 정하면 규칙에 맞게 주사위를 쌓아올리고 옆면의 최대합을 구하면 되는 문제입니다.

첫번째 주사위의 6개의 면의 숫자를 모두 돌면서 어떤 수가 윗면으로 위치했을 때 최대합을 구할 수 있는지 반복 탐색해야합니다.

여기서 각 주사위의 맞은편의 인덱스를 저장한 op 배열을 선언해서 활용합니다.

 

1. 첫번째 주사위의 윗면을 정합니다.
2. 윗면과 윗면의 맞은 편인 아랫면을 제외한 수 중에서 최대값을 구해서 따로 변수에 저장합니다.
3. 첫번째 주사위의 윗면은 두번째 주사위의 아랫면이므로 이를 통해서 옆면 중 최대값을 구할 수 있습니다.
4. 이렇게 반복하여 재귀호출을 진행하면서 첫번째 주사위의 윗면에 따른 주사위 들의 옆면의 최대값을 구합니다.
5. 이렇게 구해진 옆면의 최대합 중에서 최대값을 구하여 출력합니다.

 

문제 풀이

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

public class Main {

    static int[] op = {5, 3, 4, 1, 2, 0};
    static int[][] dice;
    static int N, MAX;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        dice = new int[N][6];

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

        MAX = -1;
        for(int i=0; i<6; i++){
            int max = 0;
            for(int j=0; j<6; j++){
                if(i==j || j==op[i]) continue;
                max = Math.max(max, dice[0][j]);
            }

            up(dice[0][i], max, 1);
        }

        System.out.println(MAX);
    }

    private static void up(int upNum, int sum, int cnt){
        if(cnt == N) {
            MAX = Math.max(sum, MAX);
            return;
        }

        int downNum = upNum;
        for(int i=0; i<6; i++){
            if(dice[cnt][i] == downNum){
                upNum = dice[cnt][op[i]];
                break;
            }
        }

        int max = 0;
        for(int i=0; i<6; i++){
            if(dice[cnt][i] == downNum || dice[cnt][i] == upNum) continue;
            max = Math.max(dice[cnt][i], max);
        }

        sum += max;
        up(upNum, sum, cnt+1);
    }
}