백준 1041번 - 주사위

문제

백준 1041번 - 주사위

아이디어

• 바닥이 보이지 않는 N^3 크기의 정육면체는 주사위 한면, 두면 최대 세면이 보이는 주사위의 개수가 정해져있다.
• 이를 구하는 과정이 복잡했는데 어쨌든 다음과 같았다.
• 한면이 보이는 경우
  - (N-2)^2(윗부분) + 4(N-2)(N-1)(옆부분 4개) = 5N^2 - 16N + 12 개
• 두면이 보이는 경우
  - 4(N-2) + 4(N-1) = 8N - 12
• 세면이 보이는 경우
  - 4개 (위쪽 꼭짓점 부분)
• 한면이 보이는 경우는 6면 중 가장 작은 값들이 보이게 하면 된다.
• 두면이 보이는 경우는 6면 중 가장 작은 두 개 값들이 보이게 하면 된다.
• 세면이 보이는 경우는 6면 중 가장 작은 세 개 값들이 보이게 하면 된다.
• 최대 세면이 보일 때 가장 작은 세 개 값들을 구하려면 마주보는 면들 중 최솟값을 구하면 된다. A와 F, B와 E, C와 D

예상 시간 복잡도

• 예상 시간 복잡도 : O(1)

코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BJ_1041 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[] dice = new int[6];
        StringTokenizer st = new StringTokenizer(br.readLine());

        int sum = 0;
        int max = 0;
        for (int i = 0; i < 6; i++) {
            dice[i] = Integer.parseInt(st.nextToken());
            sum += dice[i];
            max = Math.max(max, dice[i]);
        }

        //주사위가 1개인 경우
        if (n == 1) {
            System.out.println(sum - max);
            return;
        }

        int[] min = new int[3];
        min[0] = Math.min(dice[0], dice[5]); //A와 F
        min[1] = Math.min(dice[1], dice[4]); //B와 E
        min[2] = Math.min(dice[2], dice[3]); //C와 D

        Arrays.sort(min);

        System.out.println(
                ((min[0] + min[1] + min[2]) * 4L) + //3면이 보이는 주사위
                ((min[0] + min[1]) * (8L * n - 12)) + //2면이 보이는 주사위
                (min[0] * (5L * n * n - 16L * n + 12)) //1면이 보이는 주사위
        );
    }
}