[07.24] 백준 1041

문제 1041번 (성공)

소스코드

import java.io.*;
public class boj1041 {
    static int min = Integer.MAX_VALUE;
    static int arrmin = Integer.MAX_VALUE;
    static int arrmax = 0;
    public static void combination22(int[] arr, boolean[] visited, int depth, int n, int r){
        if(r == 0){
            int sum =0;
            for (int i = 0; i < n; i++) {
                if (visited[i] && visited[n-i-1]){
                    sum =0;
                    break;
                }
                else if(visited[i]){
                    sum += arr[i];
                }
            }
            if(sum != 0) {
                min = Math.min(min, sum);
            }
            return;
        }
        if(depth ==n){
            return;
        }
        visited[depth] = true;
        combination22(arr, visited, depth+1, n, r-1);
        visited[depth] = false;
        combination22(arr, visited, depth+1, n, r);
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(br.readLine());
        int[] arr = new int[6];
        boolean[] visited = new boolean[6];
        String[] input = br.readLine().split(" ");
        for (int i = 0; i < 6; i++) {
            arr[i] = Integer.parseInt(input[i]);
            arrmin = Math.min(arrmin, arr[i]);
            arrmax = Math.max(arrmax, arr[i]);
        }
        if(n==1){
            int sum = 0;
            for (int i = 0; i < 6; i++) {
                sum += arr[i];
            }
            sum -= arrmax;
            System.out.println(sum);
        }else {
            combination22(arr, visited, 0, arr.length, 3);
            int min3 = min;
            combination22(arr, visited, 0, 6, 2);
            int min2 = min;
            long mul2 = 8 * (n - 2) + 4;
            long mul1 = (n - 2) * (n - 1) * 4 + (n - 2) * (n - 2);
            long sum = (4 * min3) + min2 * mul2 + arrmin * mul1;
            System.out.println(sum);
        }
    }
}

풀이 접근

1. n^3 의 정육면체에는 가로 세로 높이에 각각 n개의 주사위를 가지고 만든다.
2. 문제에서 밑변을 제외하고 밖으로 보이는 숫자만 더한 값의 최소값을 구한다. 그러면 1면, 2면, 3면이 밖으로 보이는 경우가 있을 것이다.
3. 규칙을 구해보면 3면은 4개, 2면은8(n - 2) + 4 , 1면은 (n - 2) (n - 1)4 + (n - 2) (n - 2)이다
4. 1면의 경우 주사위의 가장 작은 숫자를 곱해주면 되고, 2면과 3면의 최소값을 구하기 위해 조합을 사용했다.
5. 전개도에 따라 주사위에서 마주하는 변이 포함되는 경우는 제외해야 함으로 아래와 같이 예외처리를 해준다.

if (visited[i] && visited[n-i-1]){
                    sum =0;
                    break;
                }

6. 처음에 입력을 받을 때 주사위의 가장 큰 값과 작은 값을 저장한다.
7. n=1인 경우를 제외하고, 3번부터 구해왔던 식에 따라서 sum값을 저장하고 출력한다.
8. n=1인 경우에는 6면의 숫자를 더해서 출력한다.

문제 핵심

• 두 수의 최소값과 세 수의 최소값을 전개도에 맞춰 구할 수 있는지.
• 문제에서 주어진 알고리즘을 구현할 수 있는지.
• n=1일 경우에 대한 예외처리가 있는지 (이 경우를 생각 안해서 1번 오답을 받았다.)