BOJ 2116 주사위 쌓기

사용한 알고리즘

알고리즘 설명

먼저 문제를 아래에서 부터 주사위를 쌓아 올린다고 생각하자.
옆면에는 주사위에 윗면과 아랫면을 제외한 모든 숫자가 있다.
옆면에 최대값을 얻기 위해서는 옆면에 있는 값중 최대 값을 한쪽 옆면에 몰아주면 된다.
Case1. 주사위의 윗면과 아랫면에 6이 없는 경우, 옆면 최대 값은 6
Case2. 주사위의 윗면과 아랫면에 6이 있고 5는 없는 경우, 옆면 최대 값은 5
Case3. 주사위의 옆면과 아랫면에 5와 6 모두 있는 경우, 옆면 최대값은 4
위 알고리즘으로 옆면 중 최대 값을 정하고, 처음 시작하는 주사위의 윗면의 숫자에 따라서 다른 경우의 수를 가지므로 윗면이 1~6까지 모두 판단한다.
윗면의 반대편 숫자 인덱스를 얻기 위해서 match를 사용하였다. 0번째 숫자의 맞은편은 match(0)=5로 5번째 인덱스 값이 맞은편 인덱스이다.
위 match를 이용하여 아래쪽면과 위쪽면에 숫자가 같도록 한다.
DFS로 이를 구현하면 Recursive 하게 문제를 해결해 나갈 수 있다.

풀이

// baekjoon 2116 yechan
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N=10001;
// 윗면에 매칭되는 아랜면 인덱스 0->5, 1->3, 2->4, 3->1, 4->2, 5->0
const int match[6] = {5, 3, 4, 1, 2, 0};

int N, dice[MAX_N][6], ans;

// 현재 주사위의 번호 here, parent는 현재 아래 주사위에 위쪽 번호
int dfs(int here, int parent) {
// 모든 주사위를 쌓았을 경우 종료
	if (here == N) return 0;

	int i=0;
	for (i=0; i<6; i++)
		if (dice[here][i] == parent)
			break;
// 윗면의 인덱스가 i 이고, 아랫면 인덱스가 match(i)이다.
	int up = match[i];
// 옆면 숫자중 가장 큰 숫자가 side
	int side = 0;
// Case1. 윗면과 아랫면의 가장 큰 숫자가 6이 아닌경우
	if (max(parent, dice[here][up]) != 6) side = 6;
// Case2. 윗면과 아랫면에 6이 있지만, 5는 없는 경우
	else if (min(parent, dice[here][up]) != 5) side = 5;
// Case3. 윗면과 아랫면에 5와 6이 모두 있는 경우
	else side = 4;

// 다음 주사위를 쌓기
	return dfs(here+1, dice[here][up])+side;
}

int main() {
	scanf("%d", &N);
	for (int i=0; i<N; i++)
		for (int j=0; j<6; j++)
			scanf("%d", &dice[i][j]);

	for (int i=0; i<6; i++)
		ans = max(ans,dfs(0, dice[0][i]));

	printf("%d\n", ans);
	return 0;
}