[Algorithm Problem] 주사위 (BAEKJOON: 1041)

주사위 (BAEKJOON: 1041)

이 문제는 50이하의 자연수가 각 면마다 새겨진 정육면체 주사위가 주어질 때, N * N * N 개의 주사위로 이루어진 정육면체의 한 면을 제외한 모든 면에 적힌 수의 합 중 최소가 되는 값을 구하는 것이다. 주사위는 아래와 같은 모양을 띈다.

		+---+
		| D |
	+---+---+---+---+
	| E | A | B | F |
	+---+---+---+---+
		| C |
		+---+

정육면체에서는 2면이 결정되는 순간 위상이 고정된다. 따라서 3면의 최소 값, 2면의 최소 값, 1면의 최소 값들로 구성될 수 있다. 그렇기 때문에 주사위 개수가 N * N * N 일 때, 3면의 최소 값은 고정적으로 4개, 2면의 최소 값은 (N - 2) * 4 + (N - 1) * 4개, 1면의 최소 값은 (N - 2) * (N - 1) * 4 + (N - 2) * (N - 2)개가 된다. 만약 N의 값이 3이고, A ~ F 순서로 1 ~ 6의 값이 새겨져 있다면 바닥에 27개의 주사위를 쌓았을 때, 바깥 면에 적힌 모든 수의 합의 최소값은 69이다.

풀이

#include<iostream>
#define MAXNUM 9999999999
using namespace std;

typedef unsigned long long int ulli;
int min(int a, int b) {
	if (a <= b) return a;
	else return b;
}

int main(int argc, char* argv[]) {

	ulli N;
	ulli arr[6] = { 0, }; // A, B, C, D, E, F

	cin >> N;
	if (N == 1) {
		ulli val = 0;
		ulli sum = 0;
		ulli maxVal = 0;
		
		for (int i = 0; i < 6; i++) {
			cin >> val;
			sum += val;
			if (maxVal < val) maxVal = val;
		}

		cout << sum - maxVal;
		return 0;
	}
	
	for (int i = 0; i < 6; i++) cin >> arr[i];

	ulli min3Num = MAXNUM;
	ulli min2Num = MAXNUM;
	ulli min1Num = MAXNUM;

	min3Num = min(min3Num, arr[2] + arr[0] + arr[1]);
	min3Num = min(min3Num, arr[2] + arr[1] + arr[5]);
	min3Num = min(min3Num, arr[2] + arr[5] + arr[4]);
	min3Num = min(min3Num, arr[2] + arr[4] + arr[0]);

	min3Num = min(min3Num, arr[3] + arr[0] + arr[1]);
	min3Num = min(min3Num, arr[3] + arr[1] + arr[5]);
	min3Num = min(min3Num, arr[3] + arr[5] + arr[4]);
	min3Num = min(min3Num, arr[3] + arr[4] + arr[0]);

	for (int i = 0; i < 6; i++) {
		for (int j = i + 1; j < 6; j++) {
			if (i == 0 && j == 5) continue;
			if (i == 1 && j == 4) continue;
			if (i == 2 && j == 3) continue;

			min2Num = min(min2Num, arr[i] + arr[j]);
		}
	}
	for (int i = 0; i < 6; i++) min1Num = min(min1Num, arr[i]);

	// cout << min3Num << ' ' << min2Num << ' ' << min1Num << '\n';

	ulli ans = min3Num * 4 + min2Num * (2 * N - 3) * 4 + min1Num * ((N - 2) * (N - 1) * 4 + (N - 2) * (N - 2));
	cout << ans;

	return 0;
}