[백준] 2116 - 주사위 쌓기

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

2116번: 주사위 쌓기

 

모든 경우를 다 해볼 필요가 없다.

사실 1번 주사위의 윗면만 정하면, 모든 주사위의 아래/윗 면이 정해지게 되고, 그리디 하게 남은 부분의 최댓값을 더하면 된다.

 

#include <iostream>
using namespace std;

int n, arr[10000][6];
int no[6] = { 5,3,4,1,2,0 };

int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 6; j++) {
			cin >> arr[i][j];
		}
	}
	int ans = 0;
	for (int k = 0; k < 6; k++) {
		int up = arr[0][k];
		int temp = 0;

		for (int i = 0; i < 6; i++) {
			if (i != k && i != no[k]) {
				temp = max(temp, arr[0][i]);
			}
		}

		for (int i = 1; i < n; i++) {
			int findBottomIdx = 0;
			for (int j = 0; j < 6; j++) {
				if (up == arr[i][j]) {
					findBottomIdx = j;
					break;
				}
			}
			int tempp = 0;
			for (int j = 0; j < 6; j++) {
				if (j != findBottomIdx && j != no[findBottomIdx]) {
					tempp = max(tempp, arr[i][j]);
				}
			}
			temp += tempp;
			up = arr[i][no[findBottomIdx]];
		}
		ans = max(ans, temp);
	}

	cout << ans;
}