[2116] 주사위 쌓기

🔗 문제 링크

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

🔍 문제 설명

천수는 여러 종류의 주사위를 가지고 쌓기 놀이를 하고 있다. 주사위의 모양은 모두 크기가 같은 정육면체이며 각 면에는 1부터 6까지의 숫자가 하나씩 적혀있다. 그러나 보통 주사위처럼 마주 보는 면에 적혀진 숫자의 합이 반드시 7이 되는 것은 아니다.

주사위 쌓기 놀이는 아래에서부터 1번 주사위, 2번 주사위, 3번 주사위, … 의 순서로 쌓는 것이다. 쌓을 때 다음과 같은 규칙을 지켜야 한다: 서로 붙어 있는 두 개의 주사위에서 아래에 있는 주사위의 윗면에 적혀있는 숫자는 위에 있는 주사위의 아랫면에 적혀있는 숫자와 같아야 한다. 다시 말해서, 1번 주사위 윗면의 숫자는 2번 주사위 아랫면의 숫자와 같고, 2번 주사위 윗면의 숫자는 3번 주사위 아랫면의 숫자와 같아야 한다. 단, 1번 주사위는 마음대로 놓을 수 있다.

이렇게 쌓아 놓으면 긴 사각 기둥이 된다. 이 사각 기둥에는 4개의 긴 옆면이 있다. 이 4개의 옆면 중에서 어느 한 면의 숫자의 합이 최대가 되도록 주사위를 쌓고자 한다. 이렇게 하기 위하여 각 주사위를 위 아래를 고정한 채 옆으로 90도, 180도, 또는 270도 돌릴 수 있다. 한 옆면의 숫자의 합의 최댓값을 구하는 프로그램을 작성하시오.

⚠️ 제한사항

• 주사위의 개수는 10,000개 이하이며 종류가 같은 주사위도 있을 수 있다.

---

🗝 풀이 (언어 : Java)

단순 구현으로 풀었다.

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

public class Main {
    static int max = -1, N;
    static int[][] arr;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        arr = new int[N][6];
        //N개의 주사위 정보 저장
        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++) {
            search(1, i, 0);
        }
        bw.write(String.valueOf(max));	//최대값 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //주사위를 순차적으로 쌓는 재귀 함수
    static void search(int cnt, int bottom, int sum){
        //아랫면을 마주보는 면 구하기
        int pair = pairCheck(bottom);
        int tempMax = -1;
        //옆면의 최대값 구하기
        for(int i=0;i<6;i++){
            if(i == pair || i == bottom)
                continue;
            tempMax = Math.max(tempMax, arr[cnt-1][i]);
        }
        sum += tempMax;	//최대값 더하기
        //주사위를 모두 다 쌓았을 때
        if(cnt == N){
            max = Math.max(max, sum);	//최대값 비교
            return;
        }
        //다음 주사위 쌓기 진행
        for(int i=0;i<6;i++){
            if(arr[cnt-1][pair] == arr[cnt][i]){
                search(cnt+1, i, sum);
                break;
            }
        }
    }
    //마주보는 면 인덱스 구하는 함수
    static int pairCheck(int n){
        if(n == 0)
            return 5;
        else if(n == 1)
            return 3;
        else if(n == 2)
            return 4;
        else if(n == 3)
            return 1;
        else if(n == 4)
            return 2;
        else
            return 0;
    }
}