[백준 2116] 주사위 쌓기 (C++)

문제 링크: www.acmicpc.net/problem/2116

2116번: 주사위 쌓기

1. 주의할 점

- 특정 면이 윗면일때(반대편도 동일) 옆면에 적힌 숫자의 값 중에서 최대값을 Maxi[][]에 저장해놓는다

- 가장 아래층이 정해지면 위는 경우의 수가 1가지 뿐이다(옆면의 최대값을 미리 구했기 때문)

 

2. 구현

- 주사위에 대한 정보를 Dice[] 벡터에 입력받는다

- 각 주사위 면이 윗면일때 옆면의 최대값을 Maxi[i번쨰 주사위][j번째 면(반대편 포함)]에 저장한다

- 가장 아래층의 주사위를 설정한 이후, DFS()를 통해 옆면의 최대값을 더하면서 가장 꼭대기 주사위까지 쌓은 후, Result와 Sum값을 비교한다

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int num, val, result = 0;
vector<int> dice[10000];
int maxi[10000][3];

int number[3][4] = {
	{1,2,3,4},
	{0,2,4,5},
	{0,1,3,5}
};
int rev[6] = { 5,3,4,1,2,0 };		//각각 반대편숫자 idx

void dfs(int level, int sum, int up) {
	if (level == num) {
		result = max(result, sum);
		return;
	}
	for (int i = 0; i < 6; i++) {
		int v = dice[level][i];
		if (v == up) {
			int nup = dice[level][rev[i]];
			int temp = i;
			if(i>2) temp = rev[i];
			dfs(level + 1, sum+maxi[level][temp], nup);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> num;
	for (int i = 0; i < num; i++) {
		for (int j = 0; j < 6; j++) {
			cin >> val;
			dice[i].push_back(val);
		}
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 4; k++) {
				int nv = dice[i][number[j][k]];
				maxi[i][j] = max(maxi[i][j], nv);
			}
		}
	}
	for (int i = 0; i < 6; i++) {
		int up = dice[0][i];		//제일 위 숫자
		int temp = i;
		if (i > 2) temp = rev[i];
		dfs(1, maxi[0][temp], up);
	}
	cout << result;
	return 0;
}