백준 1041 주사위 c++ (탐욕법)

문제 출처 : https://www.acmicpc.net/problem/1041

1041번: 주사위

문제

주사위는 위와 같이 생겼다. 주사위의 여섯 면에는 수가 쓰여 있다. 위의 전개도를 수가 밖으로 나오게 접는다.

A, B, C, D, E, F에 쓰여 있는 수가 주어진다.

지민이는 현재 동일한 주사위를 N3개 가지고 있다. 이 주사위를 적절히 회전시키고 쌓아서, N×N×N크기의 정육면체를 만들려고 한다. 이 정육면체는 탁자위에 있으므로, 5개의 면만 보인다.

N과 주사위에 쓰여 있는 수가 주어질 때, 보이는 5개의 면에 쓰여 있는 수의 합의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수는 50보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

알고리즘 분류

• 수학
• 그리디 알고리즘

풀이

주사위의 6면에 적힌 숫자 중, 값이 낮은 숫자만 정육면체의 표면에 노출시키는 그리디 알고리즘이다.

 

우선 정육면체가 탁자 위에 놓여 있으니 총 5면만 보이고,

n이 1일 때 정육면체는 주사위의 5개 면이 보인다.

이외에, n이 2 이상인 경우에 정육면체의 표면은, 주사위의 3개 면, 주사위의 2개 면, 주사위의 1개 면만 보이게 된다.

 

따라서 n이 1일 때를 제외하고, 우리는 주사위의 3개 면, 2개 면, 1개 면을 가장 최솟값으로 만들어서 노출시키면 된다.

그러기 위해선, 우선 주사위의 3개 면을 더했을 때의 최솟값, 2개 면을 더했을 때의 최솟값,  1개 면의 최솟값을 구해야 한다.

 

A = 3, B = 2, C = 1, D = 1, E = 3, F = 3 일 때,

서로 마주 보는 두 면에서 더 작은 값을 구한다.

min3 = min(A,F) == 3

min2 = min(B,E) == 2 

min1 = (C,D) ==1

 

여기서 가장 작은 값인 min1은 1개 면의 최솟값이 되고,

min1에 두 번째로 작은 값 min2를 더하면 2개 면의 최솟값이 되고,

min2에 세 번째로 작은 값 min3을 더하면 3개 면의 최솟값이 된다.

/*

마주 보는 두 면에서 더 작은 값을 구한 이유는,

정육면체에서 주사위의 2개 면이 보이는 경우는, 주사위의 두 면이 인접했을 때이고,

정육면체에서 주사위의 3개 면이 보이는 경우는, ㄱ ㄴ등의 격자 형태여야 하기 때문이다.

*/

위에서 구한 면이 1, 2, 3개일 때의 최솟값을 가지고, 정육면체에서 면이 1, 2, 3개 만큼 보이는 블럭의 각각 개수만큼 곱해서 더해주면 된다.

 

N=2일 때

3면이 보이는 블럭 4개

2면이 보이는 블럭 4개

1면이 보이는 블럭 1개

 

N=3일 때

3면이 보이는 블럭 4개

2면이 보이는 블럭 4+8개

1면이 보이는 블럭 8+1개

 

N=4일 때

3면이 보이는 블럭 4개

2면이 보이는 블럭 8+12개

1면이 보이는 블럭 24+4개

 

3면이 보이는 블럭 = 4개

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;
}