백준 1041 : 주사위- 도형, 그리디 알고리즘

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

 

문제

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

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

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

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

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

 

 

 

 

 

 

그림에서 파란색으로 박스친 부분을 보면 된다.  아래 박스가 전체 보이는 면을 나눈 것이고, 

위에 박스가 맨 아래 면에 숨길 수있는 면을 나타낸 것이다. 

 

 

3개 연속된 면의 최소 = threeMin , 8개

2개 연속된 면의 최소 = twoMin, 12(N-2)개

1개 면의 최소  oneMin ,  6(N-2)(N-2) 개

라고 하자.

 

그리고 각각의 면에서 가장 큰 값을 갖는 하나의 면은 따로 지정해둔다.

maxOfThree,

maxofTwo

 

 

전체 정육면체의 면의 면적 최솟값 =  threeMin * 8 + twoMin * 12(N-2) + oneMin * 6 *(N-2)^2 이다.

 

 

이때 바닥면에서 최대를 만들어서 빼주기 :maxOfThree * 4 + maxOfTwo * 4* (N-2 ) + oneMin(N-2) 이다.

 

따라서 위에 지정한 변수들만 구해주면 되는데, 

 

문제는 3개 연속된 면, 2개 연속된 면을 구하려면 '마주보는 면'은 선택하면 안된다는 거다. (연속되는 면이 아님.)

 

 

나의 경우 처음엔 DFS로 (혹은 3중 for문) 완탐을 한 다음, 마주보는 면이 있으면 pass 하는 식으로 했었는데

 

더 좋은 방법이 있어서 가져왔다.

어차피 6개면중 마주보는 면들은 쌍으로 묶어서, 그 중 최소인 면들 끼리만 구해서 요리해서 면적을 만들면 된다.

 

그렇게 해도 되는 이유는, 아래 그림에서 볼 수 있듯 분홍, 노랑, 초록인 면들 중 하나씩 고르고 나면 연속된 3개의 면을 고르는 모든 경우의 수가 나오기 떄문이다.  

그래서 각 색깔 중 작은 값들만 골라서 풀 수 있고, 그래서 그리디 알고리즘이다.

(더 큰 면적으로 답이 있다고 쳐도 더 작은 값으로 만들 수 있음)

 

정육면체가 참 신기한 도형같다.

 

 

 

 

그래서 풀이는 다음과 같다. 

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

public class Main {
    private static final int INF = 2147483647;
    private static int[] opposites =  {5,4,3,2,1,0};
    private static int[] nums = new int[6];
    private static int ThreeMin = INF;
    private static int MaxOfThree = 0;
    private static int TwoMin = INF;
    private static int MaxOfTwo = 0;
    private static int OneMin = INF;
    private static int MaxOfOne = 0; 

    private static int max(int a, int b){
        return a > b ? a : b;
    }

    private static int min(int a, int b){
        return a < b ? a : b;
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        Long N = Long.parseLong(bf.readLine());

        String[] numbers = bf.readLine().split(" ");

        int sum = 0;
        for(int i = 0; i < 6; i++){
            nums[i] = Integer.parseInt(numbers[i]);
            OneMin = min(OneMin, nums[i]);
            MaxOfOne = max(MaxOfOne, nums[i]);
            sum += nums[i];//for N == 1
        }

        if(N == 1){
            System.out.println(sum - MaxOfOne);
            return;
        }
        ArrayList<Integer> array = new ArrayList<>();

        int[] candidate = new int[3];
        candidate[0] = min(nums[0], nums[5]);
        candidate[1] = min(nums[1], nums[4]);
        candidate[2] = min(nums[2], nums[3]);

        Arrays.sort(candidate);
        ThreeMin = candidate[0] + candidate[1]  + candidate[2];
        MaxOfThree = candidate[2];

        TwoMin = ThreeMin - MaxOfThree;
        MaxOfTwo = candidate[1];
        OneMin = candidate[0];

        Long totalArea = 8 * ThreeMin + 12 * (N-2) * TwoMin + 6 *(N-2) * (N-2) * OneMin;
        Long bottomArea = 4 * MaxOfThree + 4 * (N-2) * MaxOfTwo + (N-2) * (N-2) * OneMin;

        System.out.println(totalArea - bottomArea);

        }
}