[BOJ][Java] 백준 1041번: 주사위

 

문제 설명

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

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

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

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

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

문제 풀이

이 문제의 핵심은 공식을 찾는 것 + 최솟값을 찾는 것 입니다.최솟값의 경우 A-F, B-E, C-D가 양립할 수 없으므로 두개를 비교하여 최솟값을 찾으면 되고 배열에 저장하여 정렬해주시면 됩니다.

면 3개가 노출되는 곳은 상단의 색칠된 4곳입니다. 아래의 경우 탁자에 가려져 2곳만 노출되기 때문입니다.  

면 2개만 노출되는 곳은 그림과 같이 면 3개 노출되는 곳을 제외한 모서리 부분 입니다. 이것을 공식화하면4(N-1)  + 4(N-2) => 8(N-1) + 4가 됩니다.  N-1 = 기둥 / N-2 천장 모서리 2개를 제외한 변의 개수

 

주황색: 면 3개 노출되는 상단 꼭지점 / 하늘색: 면 2개가 노출되는 모서리 변들.

천장을 제외한 나머지, 최솟값이 보이면 되는 면은 4 * (N-2) * (N-1) 입니다.

천장의 경우 양쪽 꼭지점이 이미 처리되었으므로 (N-2) * (N-2) 입니다.

즉 최솟값을 가지는 면은 4 * (N-2) * (N-1) + (N-2) * (N-2) => 5N^2-16N+12 입니다.

 

최솟값 배열을 min이라고 했을 때

min[0]: 5N^2-16N+12

min[0]+min[1]: 8N-12

min[0]+min[1]+min[2]: 4

 

이렇게 곱해주시면 답이 나오게 됩니다. 

 

풀이 코드

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

public class Main {
    private static final int[] side = new int[6];
    private static long[] totalSide = new long[3];
    private static int[] min = new int[3];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<6; i++) side[i] = Integer.parseInt(st.nextToken());

        setMinIdx();

        totalSide[0] = 4L;
        totalSide[1] = 8L * (N-2) + 4;
        totalSide[2] = 5L * (N-2) * (N-2) + 4L * (N-2);

        if(N == 1) {
            Arrays.sort(side);
            System.out.println(side[0] + side[1] + side[2] + side[3] + side[4]);
        } else {
            System.out.println(
                    totalSide[0] * (min[0] + min[1] + min[2]) +
                            totalSide[1] * (min[0] + min[1]) +
                            totalSide[2] * min[0]);
        }
    }

    private static void setMinIdx() {
        min[0] = Math.min(side[0], side[5]);
        min[1] = Math.min(side[1], side[4]);
        min[2] = Math.min(side[2], side[3]);

        Arrays.sort(min);
    }
}

 

<출처>

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

1041번: 주사위