[백준] 주사위 1041번 C++ 풀이

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

1041번: 주사위

 

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<long long> v;
long long N;
long long minsum[6];
bool visit[6];
void solve(int idx, int cnt, long long sum)
{
	if (cnt < 6)
	{
		if ((visit[0]==true&&visit[5]==true)||(visit[1]==true&&visit[4]==true)||(visit[2]==true&&visit[3]==true))
		{
			if (N != 1)
				return;
		}
		minsum[cnt] = min(minsum[cnt], sum);
	}
	else
		return;

	for (int i = idx; i < 6; i++)
	{
		if (visit[i] == false)
		{
			visit[i] = true;
			solve(i+1, cnt + 1, sum + v[i]);
			visit[i] = false;
		}
	}

}
int main(void)
{
	fill(minsum, minsum+ 6, 250000000000001);

	cin >> N;
	for (int i = 0; i < 6; i++)
	{
		int num;
		cin >> num;
		v.push_back(num);
	}


	solve(0, 0, 0);

	if (N == 1)
	{
		cout << minsum[5];
		return 0;
	}

	long long result=0;
	result += minsum[1] *((5*N*N)-(16*N)+12);
	result += minsum[2] *(8*N-12);
	result += minsum[3] * 4;
	cout << result;
}

 

전역 변수

vector<long long> v;
long long N;
long long minsum[6];
bool visit[6];

vector v에는 주사위의 눈을 넣어줍니다.

minsum의 i번째에는 i개 면의 합의 최솟값을 넣어줄 겁니다.

visit는 i개의 면을 골라주기 위해 쓸 겁니다.

 

메인 함수

int main(void)
{
	fill(minsum, minsum+ 6, 250000000000001);

	cin >> N;
	for (int i = 0; i < 6; i++)
	{
		int num;
		cin >> num;
		v.push_back(num);
	}


	solve(0, 0, 0);

	if (N == 1)
	{
		cout << minsum[5];
		return 0;
	}

	long long result=0;
	result += minsum[1] *((5*N*N)-(16*N)+12);
	result += minsum[2] *(8*N-12);
	result += minsum[3] * 4;
	cout << result;
}

먼저 minsum에 들어갈 수 있는 최댓값인 250000000000000보다 큰 25xxxxxxxxxxxxxx1을 넣어줍니다.

주사위 눈 최대가 50이고 N이 최대 1000000이니깐 최댓값이 저런 겁니다.

그리고 solve를 통해 minsum을 초기화시켜줍니다.

그 결과로 N이 1인 경우는 5개의 면이 보이는 주사위 1개가 답이니

minsum[5]를 출력

그 외 n 정육면체는

1면, 2면, 3면의 최솟값을 적절히 더하면 답을 구할 수 있습니다.

먼저 NxNxN 크기의 정육면체가 있습니다.

여기서 각 블럭은 주사위인데

N이 2 이상일 때 각 블럭은 보이는 면이 1,2,3개인 주사위들로 이루어져 있습니다.

따라서 주사위의 보이는 면이 1, 2, 3개일 때의 최솟값을 구해주어

필요한 만큼 주사위 눈의 합을 구하면 됩니다.

NxNxN 크기의 정육면체에서

 

보이는 면이 1개인 경우는 젤 윗면에 4개와 각 사이드에 6개씩이 4세트로 이루어져 있습니다.

즉 맨 윗면의 보이는 면 1개는 (N-1)*(N-1)개로 구할 수 있고

각 사이드 4세트가 있는데 한 세트는 (n-1)*(n-2) 이므로 4(n-1)(n-2)로 구할 수 있습니다.

즉 보이는 면이 1개인 주사위는 (N-1)*(N-1)+4(N-1)(N-2) = 5n^2-16n+12 개가 필요합니다.

(n-1)(n-2)

(n-1)(n-1)

 

 

보이는 면이 2개인 경우는 젤 윗면에 n-2인 부분이 4개가 있으므로 4(n-2)와 

각 사이드에 n-1개가 4개가 있으므로 4(n-1)로 4(n-2)+4(n-1) = 8n-12

n-2

n-3

 

보이는 면이 3개인 것은 맨 위에 모서리에 4개가 고정적입니다.

4개

 

따라서 아래처럼 N이 1이 아닌 경우

1, 2, 3면이 보이는 개수를 각 면이 가질 수 있는 최솟값으로 곱해주고 모두 더해주면 답이다.

long long result=0;
result += minsum[1] *((5*N*N)-(16*N)+12);
result += minsum[2] *(8*N-12);
result += minsum[3] * 4;

 

 

solve 함수

if (cnt < 6)
{
	if ((visit[0]==true&&visit[5]==true)||(visit[1]==true&&visit[4]==true)||(visit[2]==true&&visit[3]==true))
	{
		if (N != 1)
			return;
	}
	minsum[cnt] = min(minsum[cnt], sum);
}

cnt는 보이는 면의 개수를 나타낸다.

1~5면의 최소합을 구하는데

0 1 2 3 4 5
A B C D E F 일 때

A와F, B와E, C와D는 마주 보는 면으로 이것은 각 주사위 눈을 동시에 보일 수가 없으니 불가능하므로

만약 동시에 선택되어 있을 경우 불가능한 경우이니 return 해주자

단, N이 1인 경우는 AF나 BE나 CD가 마주 보고 있더라고 동시에 보일 수 있다.

 

 

아래의 코드는 cnt개를 뽑아내기 위한 코드이다.

	for (int i = idx; i < 6; i++)
	{
		if (visit[i] == false)
		{
			visit[i] = true;
			solve(i+1, cnt + 1, sum + v[i]);
			visit[i] = false;
		}
	}