[BOJ]1041번 주사위

주사위 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

18982

5257

4425

27.743%

문제

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

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

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

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

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

입력

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

출력

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

 

 

---

📝풀이 

그리디 문제이지만 주사위의 특징을 잘 알고 풀어야한다. 

왜냐하면 주사위의 면 5개를 구하는 것은 주사위를 상상하며 아이디어를 떠올려야 한다. 

알아야할 것은

• 주사위의 구성
• 계산해야 하는 요소들의 특징

주사위의 구성

 

우선 우리는 주사위면의 최소값을 구해서 그리디 연산을 해야한다. 그렇기에 주사위 면의 최소 값을 봐야하는데 

해당 그림처럼 마주보는 면으로 비교를 해줘야 최소 값을 구할 수 있다. 

        long[] sideSums = new long[3];
        sideSums[0] = Math.min(diceValues[0], diceValues[5]); // af
        sideSums[1] = Math.min(diceValues[1], diceValues[4]); // be
        sideSums[2] = Math.min(diceValues[2], diceValues[3]); // cd

위 코드는 각 면의 최소 값을 구하는 것이다. 

 

계산해야 하는 요소들의 특징

 

3 X 3 주사위를 보자

 

우리가 구해야 하는 부분은 크게 3가지 부분이다.

• 1면이 나오는 부분 : 가운데 부분 + 밑쪽 가장자리 부분
• 2면이 나오는 부분 : 나머지 가장자리 부분 + 밑쪽 꼭짓점 부분
• 3면이 나오는 부분 : 윗쪽 꼭짓점 부분

이제 각 면이 몇개 나오는지 생각해보자

• 1면이 나오는 부분 : (N-2) x (N-2) x 5 + (N-2) * 4
• 2면이 나오는 부분 : (N-2) x 8 + 4
• 3면이 나오는 부분 : 4

        long pattern1 = (N - 2) * (N - 2) * 5 + (N - 2) * 4;
        long pattern2 = (N - 2) * 8 + 4;
        long total = minSideSum * pattern1 //1면이 나오는 경우
        total += minTwoSideSum * pattern2 //2면이 나오는 겨우
        total += minThreeSideSum * 4; //3면이 나오는 경우
        System.out.println(total);

 

전체 코드 

import java.util.Arrays;
import java.util.Scanner;

public class Main { // 주사위

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long N = sc.nextLong();
        long[] diceValues = new long[6];

        long sum = 0;
        for (int i = 0; i < 6; i++) {
            diceValues[i] = sc.nextLong();
            sum += diceValues[i];
        }

        if (N == 1) {
            Arrays.sort(diceValues);
            System.out.println(sum - diceValues[5]);
            return;
        }

        long[] sideSums = new long[3];
        sideSums[0] = Math.min(diceValues[0], diceValues[5]); // af
        sideSums[1] = Math.min(diceValues[1], diceValues[4]); // be
        sideSums[2] = Math.min(diceValues[2], diceValues[3]); // cd

        long minSideSum = Long.MAX_VALUE;
        for (int i = 0; i < 6; i++) {
            if (minSideSum > diceValues[i])
                minSideSum = diceValues[i];
        }

        long minTwoSideSum = Math.min(sideSums[0] + sideSums[1], Math.min(sideSums[1] + sideSums[2], sideSums[0] + sideSums[2]));

        long minThreeSideSum = 0;
        for (int i = 0; i < 3; i++) {
            minThreeSideSum += sideSums[i];
        }

        long pattern1 = (N - 2) * (N - 2) * 5 + (N - 2) * 4;
        long pattern2 = (N - 2) * 8 + 4;
        long total = minSideSum * pattern1 + minTwoSideSum * pattern2 + minThreeSideSum * 4;
        System.out.println(total);
    }
}