[백준] 2116 주사위 쌓기

1. 문제

www.acmicpc.net/problem/2116

2116번: 주사위 쌓기

2. 접근방법

주사위를 위로 쌓아가는데 아래 주사위의 윗숫자와 위 주사위의 아래 숫자가 같게 쌓아서

그 때 만들어진 주사위 탑의 옆면이 제일 큰 값을 찾는 문제

 

첫번째 주사위를 어떻게 놔두느냐에 따라 모든 주사위의 방향이 정해지므로

총 6개 모양의 주사위가 생긴다.

이제 주사위 아랫면 인덱스를 알때 윗면을 찾아야한다. 

ABCDEF

012345

의 인덱스를 주는데

0 <-> 5

1 <-> 3

2 <-> 4

위 아래 인덱스가 이렇게 되어있는데

공식으로 만들기가 어려워

3이랑 4,  즉 C랑 D의 인덱스를 바꿔서 넣어 줬다.

0 <-> 5

1 <-> 4

2 <-> 3

이러면

5 - 아랫면 인덱스 = 윗 면 인덱스 로

구할 수 있다.

 

그 다음

대충 이런식으로 쌓인다고 할때 옆 면을 더했을 때 가장 큰 값을 찾아야 하는데

그냥 각 주사위 옆면 중 가장 큰값만 찾아서 다 더하면 된다. 

 

3. 자바 코드

package Gold;

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

public class P2116주사위쌓기 {
	static int N, dice[][], max;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		dice = new int[N][6];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 6; j++) {
				if (j == 3)
					dice[i][4] = Integer.parseInt(st.nextToken());
				else if (j == 4)
					dice[i][3] = Integer.parseInt(st.nextToken());
				else
					dice[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		// AFBDCE
		// 051324
		for (int i = 0; i < 6; i++)
			dfs(dice[0][i], 0, 0);
		System.out.println(max);
	}

	static void dfs(int down, int index, int sum) {
		if (index == N) {
			max = Math.max(sum, max);
			return;
		}
		if (sum + (N - index) * 6 <= max) {
			return;
		}
		int up = 0;
		for (int i = 0; i < 6; i++) {
			if (dice[index][i] == down) {
				up = dice[index][5 - i];
				break;
			}
		}
		int maxside = 0;
		for (int i = 0; i < 6; i++) {
			if (dice[index][i] == down || dice[index][i] == up) {
				continue;
			}
			maxside = Math.max(maxside, dice[index][i]);
		}
		dfs(up, index + 1, sum + maxside);

	}

}

4. 마치며

인덱스 위치 찾는 거랑

옆면 중 제일 큰값만 더해서 비교하면 되는 건데 

모든 면에 대해서 더해보고 검사하느라 최악 4의 10000제곱 * 6 으로 풀어서 시간초과 한번 당했다..

좀만 더 생각하자.