[BOJ 1041] 주사위

문제 링크 : https://www.acmicpc.net/problem/1041

문제

    +---+        
    | D |        
+---+---+---+---+
| E | A | B | F |
+---+---+---+---+
    | C |        
    +---+        

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

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

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

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

입력

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

출력

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

제한

시간 제한	메모리 제한
2sec	128MB

---

풀이

우선 직관적으로 문제를 이해하기 위해 실제로 쌓아보자. 너무 많이 쌓지는 말고 $N=3$ 정도만 쌓아보도록 하자.

이 상태에서 하나하나의 큐브들을 생각해보았을 때, 보이는 면의 개수가 각기 다른 것을 알 수 있다. 색깔로 구분해보면 아래와 같을 것이다.

여기서 색깔로 구분된 큐브들은 아래와 같은 특징을 가지고 있다.

색깔	위치	개수	실제 갯수	보이는 면의 수
노란색	상단 꼭짓점	$4$	$4$	$3$
연두색	하단을 제외한 각 모서리	$8$	$8 \times (N-2)$	$2$
빨간색	하단 꼭짓점	$4$	$4$	$2$
하늘색	큐브 면 중앙	$5$	$5 \times (N-2)^2$	$1$
검정색	큐브 하단 모서리	$4$	$4 \times (N-2)$	$1$

그림을 보면 알 수 있듯, 연두색과 빨간색 큐브는 사실상 동일한 면을 보여준다고 볼 수 있으며, 하늘색과 검정색 큐브 또한 동일한 면을 보여준다고 볼 수 있다. 즉, 우리는 인접한 면에 적힌 수의 합이 가장 작은 경우를 미리 계산해두고 그 갯수만큼 헤아려 정답을 알아낼 수 있다!

찾아야하는 큐브의 종류가 3종류이므로, 우선 모두 계산해두도록 하자. 우선 한 면의 합이 최소인 경우를 찾는 방법은 간단하다.

#define INF 987654321987654321
ll cube_number[MAX_SIZE_OF_CUBE]; // MAX_SIZE_OF_CUBE = 6

min_for_1_face = INF;
for (int i = 0; i < MAX_SIZE_OF_CUBE; ++i) {
    min_for_1_face = min(min_for_1_face, cube_number[i]);
}

다음으로는 두 면의 합이 최소인 경우를 찾는다. 같은 방법으로 진행하면 되지만, 반대의 면의 합은 고려하면 안된다. 문제에서 제시한 순서대로 주사위의 면을 기록해두었다면, 주사위의 반대 면에 대해 하나의 쌍으로 기록한다면 (A, F), (B, E), (C, D)이라는 것을 알 수 있다. 각 문자를 $0$부터 $5$까지의 숫자로 치환한다면, 각 쌍의 합이 $5$라는 결과를 얻을 수 있다. 반대 면을 확인하는 간단한 방법이 생겼다!

min_for_2_face = INF;
for (int i = 0; i < MAX_SIZE_OF_CUBE; ++i) {
    for (int j = i + 1; j < MAX_SIZE_OF_CUBE; ++j) {
        if (i + j != 5) {
            min_for_2_face = min(min_for_2_face, cube_number[i] + cube_number[j]);
        }
    }
}

마찬가지로 세 면의 합이 최소인 경우도 찾아주도록 하자. 합하려는 면들 중 반대 쌍이 없기만 하면 된다.

min_for_3_face = INF;
for (int i = 0; i < MAX_SIZE_OF_CUBE; ++i) {
    for (int j = i + 1; j < MAX_SIZE_OF_CUBE; ++j) {
        for (int k = j + 1; k < MAX_SIZE_OF_CUBE; ++k) {
            if (i + j != 5 && j + k != 5 && k + i != 5) {
                min_for_3_face = min(min_for_3_face, cube_number[i] + cube_number[j] + cube_number[k]);
            }
        }
    }
}

이제 이 정보를 종합하여 문제에서 원하는 답을 얻어낼 수 있다. 그저 각 큐브의 개수만큼 세서 더하면 끝이다! 하지만 그대로 제출하면 아마 틀릴 것이다. 예외 케이스가 하나 있기 때문. $N=1$인 경우 위 가설이 적용되지 않는다. 따로 생각해보면 $N=1$인 경우 한 면을 제외한 다른 모든 면이 보인다는 것을 알 수 있고, $\sum_i face[i] - \text{min_for_1_face}$로 계산할 수 있다.

소스코드

Github Link : Source Code

참고 알고리즘 :