[Gold 5] 1041번 주사위

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

1041번: 주사위

 

이 문제는 그리디 알고리즘을 활용해면 해결할 수 있다.

 

문제 접근 시 주사위가 보이는 면만 계산하면 된다.

이유는 최소 값을 구하기 때문에 A, B, C, D, E, F 의 값중 가장 작은 값 3개를 뽑고 

3개면이 보이는 경우, 2개면이 보이는 경우, 1개면이 보이는 경우를 계산하면 된다.

 

N = 1인 경우는 작은 면 순서대로 5개의 면만 더하면 된다.

N = 2 이상부터는 보이는 면을 계산한다.

 

N = 2인 경우

3개 면 : 4개

2개 면 : 4개

1개 면 : 0개

 

N = 3인 경우

3개 면 : 4개 

2개 면 : 4 + 8면

1개 면 : 8 + 1면

 

N = ?인 경우

3개 면 : 4개 (3개면이 보이는 경우는 모서리에 해당하는 경우만 존재)

2개 면 : 4 * (N-1) + 4 * (N-2)개

1개 면 : 4 *  ((N-1)*(N-2))+(N-2)*(N-2))개

 

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	long long  n;
	long long answer = 0;
	cin >> n;
	int arr[6];
	int max_num = 0;
	for (int i = 0; i < 6; i++) {
			cin >> arr[i];
			answer += arr[i];
			max_num = max(max_num,arr[i]);
	}
	//n이 1인 경우 주어진 주사위의 가장 큰 값을 제외한 모든 값을 더한다.
	if (n == 1) {
		cout << answer - max_num;
	}
	else {
		answer = 0;
		arr[0] = min(arr[0], arr[5]);
		arr[1] = min(arr[1], arr[4]);
		arr[2] = min(arr[2], arr[3]);
	
		sort(arr, arr + 3);
		int sum1 = arr[0];
		int sum2 = sum1 + arr[1];
		int sum3 = sum2 + arr[2];


		answer += sum3 * 4;
		answer += sum2 * (4 * (n - 2) + 4 * (n - 1));
		answer += sum1 * (4 * (n - 1)*(n - 2) + (n - 2)*(n - 2));

		cout << answer;
	}
	return 0;
}