[백준] 1041번. 주사위(JAVA)

문제

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

---

풀이(20분)

import java.io.*;
import java.util.*;

public class Main {

    private static long n, oneFaceMin, twoFaceMin, threeFaceMin, maxFaceValue = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        int[] faces = new int[6];
        int totalSum = 0;
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 6; i++) {
            faces[i] = Integer.parseInt(st.nextToken());
            maxFaceValue = Math.max(faces[i], maxFaceValue);
            totalSum += faces[i];
        }
        
        if (n == 1) {
            System.out.println(totalSum - maxFaceValue);
            return;
        }
        
        long minAF = Math.min(faces[0], faces[5]);
        long minBE = Math.min(faces[1], faces[4]);
        long minCD = Math.min(faces[2], faces[3]);
        
        threeFaceMin = minAF + minBE + minCD;
        twoFaceMin = Math.min(minAF + minBE, Math.min(minBE + minCD, minAF + minCD));
        oneFaceMin = Math.min(minAF, Math.min(minBE, minCD));
        
        System.out.println(calculateTotal());
    }
    
    private static long calculateTotal() {
        long oneFaceCount = 4 * (n - 1) * (n - 2) + (n - 2) * (n - 2);
        long twoFaceCount = 4 * (n - 2) + 4 * (n - 1);
        long threeFaceCount = 4;
        
        return oneFaceCount * oneFaceMin + twoFaceCount * twoFaceMin + threeFaceCount * threeFaceMin;
    }
}

---

문제 풀이 전략

 

코드에 주석을 작성하는 것보다 실제 풀이 접근이 더욱 중요하다고 생각하여 글을 잘 따라와 보자.

 

첫 번째 주요한 접근은 주사위들을 어떻게 쌓아야 하는지에 대한 전략이 존재하지 않는다는 것이다.

그 말은 막 쌓아도 되니까 보이는 면만 최소로 하자!라는 것.

그렇다면 우리는 어떤 구조가 만들어지는지에 집중해 보자.

 

다음과 같이 n = 3 인 큐브가 존재한다고 생각해 보자. 

 

하나의 면이 보이는 경우

빨간색으로 칠해진 부분은 하나의 면만 보일 것이다. 

옆으로 네 개의 면은 (n-2) * (n-1) 개일 것이고, 위의 면은 (n-2) * (n-2)이다.

즉, 하나의 면만 보이는 것의 개수는 5n^2 - 16n + 12가 된다.

 

두 개의 면이 보이는 경우

 

파란색으로 체크된 부분은 두개의 면이 보이는 것이다.

옆으로 네 개의 기둥은 (n-1) * 4개가 있을 것이고, 윗 면의 옆 라인은 (n-2) * 4개가 있을 것이다. 여기서 면의 개수를 말하는 것이 아닌 사각형의 개수라는 것을 인지하자.

 

세 개의 면이 보이는 경우

 

마지막으로 세개의 면이 보이는 경우는 윗면의 모서리들일 것이다. 총 4개가 존재한다.

 

검산해 보면 한 개의 면이 보이는 정육면체 5n^2 - 16n + 12개, 두 개의 면이 보이는 정육면체 8n - 12, 3개의 면이 보이는 정육면체 4개

즉, 면의 개수를 곱해서 더하면 5n^2를 만족시키게 된다.

 

---

여기까지 이해했다면, 저 면들의 최솟값을 어떻게 구할지로 마무리하자.

 

각자 마주 보는 면 중 어떤 값이 작은 지를 먼저 구한다.

예를 들어, a와 d가 마주 본다면 a와 d 중 무엇이 작은지 구한다.

그렇게 나온 결과가 a, b, c라고 하자.

 

그렇다면 세 개의 면의 합이 가장 작은 경우는 a+b+c가 될 것이다.

어떻게 그럴까? 각자 마주 보는 면이 있다면 나머지 면과는 반드시 마주하게 된다는 뜻이다.(정육면체이고, 자기 자신과 마주보는 면을 빼면 모두 인접하다.)

두 개의 면의 합이 가장 작은 경우는 a, b, c중 a+b, a+c, b+c중에 존재할 것이다.

마지막으로 한 면은 a,b,c 중에 구하면 된다.

 

최종적으로 계산해 둔 면의 개수와 함께 계산해 주면 된다