[백준] 2116번 : 주사위쌓기 - 자바(JAVA)

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

2116번: 주사위 쌓기

 

문제 해석

주사위는 1~6까지의 숫자가 적혀있다.
하지만 마주 보는 면의 숫자의 합이 반드시 7이 되는 주사위가 아니다.

 

아래에서부터 1번 주사위, 2번 주사위, 3번 주사위,... 의 순서로 주사위를 쌓는다.

 

이때 다음과 같은 규칙이 존재한다.

 

서로 붙어 있는 두 개의 주사위에서 아래에 있는 주사위의 윗면에 적혀 있는 숫자 = 위의 있는 주사위의 아랫면에 적힌 수 (단 1번 주사위는 마음대로 놓을 수 있다.)

 

이렇게 주사위를 쌓았을 때 사각 기둥에는 4개의 긴 옆면이 있다.

4개의 옆면 중에서 어느 한 면의 숫자가 합이 최대가 되도록 주사위를 쌓고자 한다.

이렇게 하기 위해 주사위의 위아래를 고정한채로 90,180,270도 돌릴 수 있을 때 한 옆면의 숫자의 합의 최댓값을 구하라.

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

 

문제 풀이 전 설계

주사위의 옆면의 합이 최대값이 되려면 주사위의 위/아래 면의 값이 가장 작아야 한다.

또한 주사위를 이어붙이기 위해서는 윗면에 적힌 숫자 = 아랫면에 적힌 숫자가 같아야 한다.

주사위의 개수가 10,000개일수도있으므로 완전 탐색은 불가능해 보인다.

 

Greedy 알고리즘으로 접근해보자

 

만약 주사위의 위/아래가 가장 작은 값으로만 만들어서 이어 붙인다면 자연스럽게 옆면에서 최댓값을 구할 수 있지만

문제는 그렇게 했을 때 주사위를 이어 붙이지 못할 수도 있다.

 

문제를 잘못 이해하고 있었습니다.

주사위를 놓는 순서를 무작위로 할 수 있는 줄 알았는데 주사위를 놓는 순서는 지정되어있었습니다.

따라서 주사위의 윗면이 1~6이 경우 6가지가 존재하므로 6가지 경우의 수를 완전 탐색으로 접근합니다.

이후 윗면의 숫자가 정해지면 그다음부터는 주사위들이 차곡차곡 정해진대로 쌓이게 됩니다.

 

코드

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

public class Main_2116_주사위쌓기 {

	static class Dice {
		int[] numbers;

		public Dice(int[] numbers) {
			super();
			this.numbers = numbers;
		}

		@Override
		public String toString() {
			return "Dice [numbers=" + Arrays.toString(numbers) + "]";
		}

	}

	static final int DICE_NUMBER = 6;
	static Dice[] dices;
	static int result;

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int diceCount = Integer.parseInt(br.readLine());

		StringTokenizer st = null;
		dices = new Dice[diceCount];
		for (int i = 0; i < diceCount; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int[] tempNumbers = new int[DICE_NUMBER];
			for (int j = 0; j < DICE_NUMBER; j++) {
				tempNumbers[j] = Integer.parseInt(st.nextToken());
			}
			dices[i] = new Dice(tempNumbers);			
		}

		for (int downSideIndex = 0; downSideIndex < DICE_NUMBER; downSideIndex++) {
			// 1번째 주사위 아랫면 지정
			
			int upSideNum = findUpSideNum(0,downSideIndex);
			int downSideNum = dices[0].numbers[downSideIndex];			
			int tempResult = 0;
			//윗면 아랫면 제외하고 최댓값 탐색
			int sideMaxNum = findSideMaxNum(upSideNum, downSideNum);
			tempResult += sideMaxNum;			
			
			// 1번째 주사위 위로 순서대로 주사위 쌓기
			for (int diceNum = 1; diceNum < diceCount; diceNum++) {				
				
				for (int k = 0; k < DICE_NUMBER; k++) {
					if (dices[diceNum].numbers[k] == upSideNum) {
						// 규칙에 맞는 수를 찾으면 해당 위치 주사위 반대면으로 upSideNum을 Update
						upSideNum = findUpSideNum(diceNum,k);
						downSideNum = dices[diceNum].numbers[k];
						break;
					}
				}
				// 아랫면 윗면 찾았으니까 두 면 제외하고 최대값탐색
				
				sideMaxNum = findSideMaxNum(upSideNum, downSideNum);
				tempResult += sideMaxNum;
			}

			result = Math.max(result, tempResult);

		}
		System.out.println(result);

	}

	private static int findSideMaxNum(int upSideNum, int downSideNum) {
		int sideMaxNum = Integer.MIN_VALUE;
		for (int k = 1; k <= DICE_NUMBER; k++) {
			if (k == upSideNum || k == downSideNum) {
				continue;
			}
			sideMaxNum = Math.max(sideMaxNum, k);
		}
		return sideMaxNum;
	}

	private static int findUpSideNum(int diceNum, int downSideIndex) {

		int upSideNum = 0;
		// A B C D E F 입력
		// A==F와 대칭 / B == D와 대칭 / C==E와 대칭
		switch (downSideIndex) {
		case 0:// A
			upSideNum = dices[diceNum].numbers[5];
			break;
		case 1:// B
			upSideNum = dices[diceNum].numbers[3];
			break;
		case 2:// C
			upSideNum = dices[diceNum].numbers[4];
			break;
		case 3:// D
			upSideNum = dices[diceNum].numbers[1];
			break;
		case 4:// E
			upSideNum = dices[diceNum].numbers[2];
			break;
		case 5:// F
			upSideNum = dices[diceNum].numbers[0];
			break;
		}
		return upSideNum;
	}

}