백준 1041번: 주사위

백준 온라인 저지(BOJ) 1041번 문제

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

1. 문제 요약

주사위 전개도와 각 면의 숫자들이 주어진다.

주사위 N^3개를 가지고 대형 주사위를 만들었을 때

바닥을 제외한 5개의 면에서 보이는 숫자의 합의 최소를 구하여라.

2. 알고리즘

3면이 보이는 주사위, 2면이 보이는 주사위, 1면이 보이는 주사위가 존재하게 된다.

각각의 개수는

3면이 보이는 주사위의 경우 4개

2면이 보이는 주사위의 경우 $4(N - 1) + 4(N - 2)$개

1면이 보이는 주사위의 경우 $4(N - 1)(N - 2) + (N-2)^2$개이다.

3면이 보이는 주사위 1개의 최솟값은 각 마주보는 3쌍의 면 중 작은값을 더한 값이고,

2면이 보이는 주사위는 마주보는 면이 아닌 두 면의 합 중 최솟값,

1면이 보이는 주사위는 전체 중 최솟값이다.

곱한 뒤 더하면 완료된다.

1일 때는 예외로 처리해주고, 수가 크므로 long long을 사용한다.

3. 코드

#define MIN(A, B) (A < B ? A : B)
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int a[6], min1, min2, min3;
	long long N, n1, n2, n3 = 4, sum = 0;
	cin >> N;
	for (int i = 0; i < 6; ++i) cin >> a[i];
	
	if (N == 1) {
		sort(a, a + 6);
		for (int i = 0; i < 5; ++i) sum += a[i];
	}
	else {
		a[0] = MIN(a[0], a[5]);
		a[1] = MIN(a[1], a[4]);
		a[2] = MIN(a[2], a[3]);
		sort(a, a + 3);
		min3 = a[0] + a[1] + a[2];
		min2 = a[0] + a[1];
		min1 = a[0];

		n1 = (N - 1) * (N - 2) * 4 + (N - 2) * (N - 2);
		n2 = (N - 1) * 4 + (N - 2) * 4;

		sum += n1 * min1;
		sum += n2 * min2;
		sum += n3 * min3;
	}
	cout << sum << endl;
	return 0;
}