2116. 주사위 쌓기

문제 링크

1. 문제 해결

 1. 1번 주사위 윗면의 숫자는 2번 주사위 아랫면의 숫자와 같고, 2번 주사위 윗면의 숫자는 3번 주사위 아랫면의 숫자와 같아야 한다.
 2. 1번 주사위는 마음대로 놓을 수 있다.
 3. 주사위의 개수는 최대 1만개이다.

가장 쉽게 생각할 수 있는 방법은 아래와 같다.

1. 규칙에 맞게 주사위를 다 둔다.
2. 다 쌓아 놓은 주사위를 가지고 각 주사위의 옆면을 돌려가면서 최댓값을 구한다.

위와 같이 진행할 경우, 시간 초과가 발생할 것이다.
이유는 단순하다. 주사위의 개수가 1만개 이하이기 때문이다.
각 주사위의 선택지는 "돌린다", "안돌린다" 두 가지인데 주사위의 개수가 1만개 일 경우, 2^10000이 된다.

1-1. 모든 동작을 구현할 것에 초점을 두지 말자.

각 주사위를 개개별로 돌릴 수 있으며 회전은 90도, 180도, 270도 회전한다.

즉, 각각의 주사위를 회전할 필요 없이 현재 정해진 위,아래 면을 제외한 나머지 옆면 중 최댓값을 구하면 된다.

1-2. 구현 방법

따라서, 우리가 최종적으로 구현해야 할 것은 아래와 같다.

- 1번 주사위를 A~F 면에 해당되는 숫자를 아래로 둔다.
- 1번 규칙을 따르기 위해 현재 주사위의 위, 아래를 구한다.
- 위, 아래를 제외한 나머지 옆 면의 값들 중 최댓값을 구한다.

위와 같이 구현할 경우, 시간 복잡도는 O(6N) => O(n)이 된다.

2. 소스 코드

//주사위 쌓기
import java.util.*;
import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());

		int[][] dices = new int[n][];

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

		int ans = 0;
		
		for(int i = 0 ; i< dices[0].length; i++) {
			int down_idx = findDownIdx(dices[0][i],dices[0]);
			int up_idx = findUpIdx(down_idx);
			
			int max_val = findMaxValue(dices[0],down_idx,up_idx);
			max_val += pileDices(dices,n,dices[0][up_idx]);
			
			ans = Math.max(ans, max_val);
		}

		System.out.println(ans);
	}

	private static int pileDices(int[][] dices, int n, int upNumber) {
		int ret = 0;

		for (int i = 1; i < n; i++) {
			int down_idx = findDownIdx(upNumber, dices[i]); // 현재 쌓으려고 하는 주사위의 아래 인덱스
			int up_idx = findUpIdx(down_idx);
			
			int max_val = findMaxValue(dices[i],down_idx,up_idx);
			
			ret += max_val;
			upNumber = dices[i][up_idx];
		}
		
		return ret;
	}
	
	private static int findMaxValue(int [] dice, int d, int u) {
		int max = 0;
		
		for(int i =0 ; i < dice.length ; i++) {
			if(d != i && u != i) {
				//위, 아래 인덱스가 아닌 경우
				max = Math.max(max, dice[i]);
			}
		}
		
		return max;
	}

	private static int findUpIdx(int downIdx) {
		if (downIdx == 0 || downIdx == 5) {
			if (downIdx == 0)
				return 5;
			return 0;
		}
		if (downIdx == 1 || downIdx == 3) {
			if (downIdx == 1)
				return 3;
			return 1;
		}
		if (downIdx == 2 || downIdx == 4) {
			if (downIdx == 2)
				return 4;
			return 2;
		}

		return 0;
	}

	private static int findDownIdx(int target, int[] dices) {
		for (int i = 0; i < dices.length; i++) {
			if (target == dices[i])
				return i;
		}

		return -1;
	}
}