스터디 23/01/07 2116 : 주사위 쌓기

2116번: 주사위 쌓기 (acmicpc.net)

2116번: 주사위 쌓기

풀이
가장 아래의 주사위의 밑면이 결정되면 나머지 주사위들의 밑면은 고정이 되고 옆면만 바뀌게 된다.
각 주사위들의 밑면에 대해 최대로 올 수 있는 옆면의 값을 미리 구해놓고 시작 주사위의 6면에 대해서 모든 경우를 탐색한다. 

시간복잡도 : O(6 * N), N <= 10^4

#include<bits/stdc++.h>
#include<time.h>


#define MAX 1000000007
#define INF 2000000000
#define MOD 1000000007 
using namespace std;
typedef long long ll;
typedef pair<int, int > pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

int dx[8] = { 0, -1, 0, 1, 1, 1, -1, -1 };
int dy[8] = { -1, 0, 1, 0, -1, 1, 1, -1 };

/*
int dx[2][6] = {
    {1, -1, 0, 0 ,1, -1},
    {1, -1, 0, 0, -1, 1}
};
int dy[2][6] = {
    {0, 0, 1, -1 ,1, -1},
    {0, 0, 1, -1, 1, -1}
};*/

//int dx[8] = { -1, -1, 1, 1, -2, -2, 2, 2 };
//int dy[8] = { 2, -2, 2, -2, -1, 1, -1, 1 };

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
}
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }

struct Node {
    int next = 0;
    int mx = 0;
};
struct Dice {
    Node num[7];
};
Dice v[10001];
int main() {
    init();
    int ans = 0;
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        int input[6];
        for (int j = 0; j < 6; j++) {
            cin >> input[j];
        }
        v[i].num[input[0]].next = input[5];
        v[i].num[input[5]].next = input[0];
        v[i].num[input[0]].mx = v[i].num[input[5]].mx
            = max(input[1], max(input[2], max(input[3], input[4])));

        v[i].num[input[1]].next = input[3];
        v[i].num[input[3]].next = input[1];
        v[i].num[input[1]].mx = v[i].num[input[3]].mx
            = max(input[0], max(input[2], max(input[4], input[5])));

        v[i].num[input[2]].next = input[4];
        v[i].num[input[4]].next = input[2];
        v[i].num[input[2]].mx = v[i].num[input[4]].mx
            = max(input[0], max(input[1], max(input[3], input[5])));
    }

    for (int i = 1; i <= 6; i++) {
        int x = i;
        int sum = 0;
        for (int j = 0; j < n; j++) {
            sum += v[j].num[x].mx;
            x = v[j].num[x].next;
        }
        ans = max(ans, sum);
    }
    cout << ans;
}