문제 설명
+---+
| D |
+---+---+---+---+
| E | A | B | F |
+---+---+---+---+
| C |
+---+
주사위는 위와 같이 생겼다. 주사위의 여섯 면에는 수가 쓰여 있다. 위의 전개도를 수가 밖으로 나오게 접는다.
A, B, C, D, E, F에 쓰여 있는 수가 주어진다.
지민이는 현재 동일한 주사위를 N3개 가지고 있다. 이 주사위를 적절히 회전시키고 쌓아서, N×N×N크기의 정육면체를 만들려고 한다. 이 정육면체는 탁자위에 있으므로, 5개의 면만 보인다.
N과 주사위에 쓰여 있는 수가 주어질 때, 보이는 5개의 면에 쓰여 있는 수의 합의 최솟값을 출력하는 프로그램을 작성하시오.
https://www.acmicpc.net/problem/1041
제한 사항
풀이
문제를 요약하면 주사위에 대한 정보가 주어졌을 때 주사위를 적절히 배치하여 보이는 면의 합을 최소로 만들면 된다.
주사위를 배치하는 방법은 N^3의 크기를 쌓아올려 육면체를 만든 것이다.
즉, 주사위를 배치한다면 한 면은 바닥에 붙어 보이지 않을 것이고 보이는 면은 정해져 있게 된다.
이 말이 무슨말이냐면 가장 위에 있는 주사위들을 생각해 보자.
N = 3이라면 모서리 4개의 주사위는 세 면이 보인다.
그리고 모서리 옆에 있는 주사위 4개는 두 면이 보인다.
마지막으로 가운데 있는 주사위 1개는 한 면만 보인다.
이런 방식으로 생각해 본다면 주사위를 배치하는 경우 보이는 면들은 정해져 있게 된다.
즉, 보이는 면의 합을 최소로 만들기 위해서는 보이는 면의 개수에 따라 최솟값을 구해놓고 이용하면 된다.
보이는 면의 최대는 3개이다. 이는 가장 위에 있는 층의 모서리에 있는 주사위들이다.
long long ans = sum[3] * 4;그리고 그 아래에 있는 N-1개의 층의 기둥에 있는 주사위는 두 면씩 보이게 된다.
그리고 가장 위에 있는 층의 테두리도 마찬가지이다.
ans += sum[2] * ((N - 2) * 4 + (N - 1) * 4);마지막으로 하나만 보이는 주사위는 N-1개의 층에서 테두리 부분을 제외한 N-2개씩 총 네 면이 있을 것이다.
거기다 가장 위에 있는 층은 N-2 * N-2개의 주사위가 있을 것이다.
ans += sum[1] * ((N - 1) * (N - 2) * 4 + (N - 2) * (N - 2));
이제 sum만 구하면 해결된다.
우선 2개씩 보이는 면의 최솟값을 구하는 방법은 주사위를 접었을 때 붙어있는 면의 합 중 최소를 선택하면 된다.
생각해 보면 마주 보는 면만 제외하면 모든 면은 붙어있다.
이는 주사위의 규칙(?)인데 마주보는 면의 합이 일정하다는 것이다.
지금은 0~5로 A, B, C, D, E, F를 표현할 수 있고 두 면의 합이 5가 된다면 두 면은 마주보는 면이라고 판정할 수 있다.
즉, 마주보는 면의 합이 5가 아니면 붙어있는 면들이며 이 면들의 합의 최솟값을 고르면 된다.
//2개 조합
for (int i = 0; i < 6; i++)
{
for (int j = 0; j < 6; j++)
{
if (i == j) continue;
if (i + j == 5) continue;
sum[2] = min(sum[2], dice[i] + dice[j]);
}
}
3개의 면을 고르는 방법은 간단하다.
직접 만들어 보면 된다.
경우의 수가 몇 개 없기 때문이다.
+---+
| D |
+---+---+---+---+
| E | A | B | F |
+---+---+---+---+
| C |
+---+
ABC, ABD, ACE, ADE, BCF, BDF, CEF, DEF
//3개 조합
sum[3] = min(sum[3], dice[0] + dice[1] + dice[2]);
sum[3] = min(sum[3], dice[0] + dice[1] + dice[3]);
sum[3] = min(sum[3], dice[0] + dice[2] + dice[4]);
sum[3] = min(sum[3], dice[0] + dice[3] + dice[4]);
sum[3] = min(sum[3], dice[1] + dice[2] + dice[5]);
sum[3] = min(sum[3], dice[1] + dice[3] + dice[5]);
sum[3] = min(sum[3], dice[2] + dice[4] + dice[5]);
sum[3] = min(sum[3], dice[3] + dice[4] + dice[5]);
이렇게 구한 값들과 앞에서 구한 계산식을 이용하여 답을 구하면 된다.
단, N이 1일 때는 논리가 적용이 안되기 때문에 따로 처리해야 한다.
최댓값만 제외하고 모두 더하면 된다.
전체 코드
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9
using namespace std;
long long N;
vector<long long> dice(6);
vector<long long> sum(4, 50*3);
int main()
{
INPUT_OPTIMIZE;
cin >> N;
for (int i = 0; i < 6; i++)
{
cin >> dice[i];
sum[1] = min(sum[1], dice[i]);
}
if (N == 1)
{
sort(dice.begin(), dice.end());
int sum = 0;
for (int i = 0; i < 5; i++)
{
sum += dice[i];
}
cout << sum;
return 0;
}
//2개 조합
for (int i = 0; i < 6; i++)
{
for (int j = 0; j < 6; j++)
{
if (i == j) continue;
if (i + j == 5) continue;
sum[2] = min(sum[2], dice[i] + dice[j]);
}
}
//3개 조합
sum[3] = min(sum[3], dice[0] + dice[1] + dice[2]);
sum[3] = min(sum[3], dice[0] + dice[1] + dice[3]);
sum[3] = min(sum[3], dice[0] + dice[2] + dice[4]);
sum[3] = min(sum[3], dice[0] + dice[3] + dice[4]);
sum[3] = min(sum[3], dice[1] + dice[2] + dice[5]);
sum[3] = min(sum[3], dice[1] + dice[3] + dice[5]);
sum[3] = min(sum[3], dice[2] + dice[4] + dice[5]);
sum[3] = min(sum[3], dice[3] + dice[4] + dice[5]);
long long ans = sum[3] * 4;
ans += sum[2] * ((N - 2) * 4 + (N - 1) * 4);
ans += sum[1] * ((N - 1) * (N - 2) * 4 + (N - 2) * (N - 2));
cout << ans;
return 0;
}