[백준 1041] 주사위

요구사항

주사위 를 n*n*n으로 쌓았을때, 각 면에 적힌 최소 합구하기

 

풀이

그리디하게 접근하는게 제일 빠른거 같다

3개 면 선택하여 최소 값

2개 면 선택하여 최소 값

각 면의 최소 값

면이 나오는 횟수에 따라 더해주면 된다

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long ll;
ll N;
ll map[7];
ll visit[7];
vector<int> v;
ll minv3 = 987654321;
ll minv2 = 987654321;
void get3() {
	for (int i = 0; i < 6; i++) {
		for (int j = i+1; j < 6; j++) {
			for (int k = j+1; k < 6; k++) {
				if (i == 0)
				{
					if (j == 5 || k == 5)
					{
						continue;
					}
				}
				if (i == 1)
				{
					if (j == 4 || k == 4)
					{
						continue;
					}
				}
				if (i == 2)
				{
					if (j == 3 || k == 3)
					{
						continue;
					}
				}
				if (j == 2) {
					if (k == 3) continue;
				}
				if (j == 4)
					if (k == 5) continue;
				if (j == 1) if (k == 4) continue;
				
				minv3 = min(minv3, (map[i] + map[j] + map[k]));
			//	cout << i << " " << j << " " << k << endl;
			}
		}
	}
	minv3 = min(minv3, (map[5] + map[3] + map[4]));
	minv3 = min(minv3, (map[5] + map[2] + map[4]));
}
void get2() {
	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;
			minv2 = min(minv2, map[i] + map[j]);
		}
	}
}
int main() {
	
	scanf("%lld", &N);
	for (int i = 0; i < 6; i++) {
		scanf("%lld", &map[i]);
	}

		minv3 = 987654321;
		minv2 = 987654321;

		//int minsum = map[0] + map[1] + map[2];
		get3();
		get2();
		ll result = 0;
	
		if (N == 1) {
			sort(map, map + 6);
			result = map[0] + map[1] + map[2] + map[3] + map[4];
		}
		else {
			//	cout << 4 * minv3 + ((2 * n - 3) * 4 * minv2 )+ ((pow(n - 2, 2) + (n - 2)*(n - 1)) * 4 * map[0]) << endl;
			sort(map, map + 6);
			long long min1 = map[0] * (N - 2) * (N - 1) * 4 + map[0] * (N - 2) * (N - 2);
			long long min2 = minv2 * (N - 1) * 4 + minv2 * (N - 2) * 4;
			long long min3 = minv3 * 4;
			result = min1 + min2 + min3;
			//	cout << min1 << " " << minv2 << " " << minv3 << endl;

		}
		cout << result << endl;
}