1041번 주사위

문제

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

풀이

큐브로 생각해서 풀면 쉽습니다. 문제의 주사위를 블록으로 호칭하겠습니다.

N 크기의 정육면체는 N=1 인 경우를 제외하고는 다음과 같이 구성됩니다.

• 모서리 블록 + 모서리를 제외한 테두리 블록(N=2 제외)+ 테두리 안쪽 블록(N=2 제외)

각 부분의 블록이 보여주는 면은 다음과 같습니다.

• 모서리 = 3면
• 테두리 = 2면
• 안쪽 = 1면

문제는 바닥면을 제외한 5 면의 최소합을 구하는 것입니다.

그러면 모서리, 테두리, 안쪽블록이 가질수 있는 면의 최소합을 구한 다음 각 구성의 개수만큼 곱해서 더해주면 됩니다.

int minOne; // 안쪽인 1면 최소합
int minTwo; // 테두리인 2면 최소합
int minThree; // 모서리인 3면 최소합

모서리의 경우 바닥면은 계산하지 않기 때문에 아래와 같은 식으로 구할 수 있습니다.

• 3면의 최소합 * 위면의 모서리 블록 4개 + 2면의 최소합 * 아랫면의 모서리 블록 4개

테두리의 경우도 바닥면으로 인해서 다음과 같은 식으로 구할 수 있습니다.

• 테두리(N)에서 모서리 2개를 제외한 개수 * ( 2면의 최소합 * 위와 옆면의 테두리블록 8개 + 1면의 최소합 * 아랫면의 테두리블록 4개)

안쪽의 경우 바닥면을 제외하고 구하면 됩니다.

• 테두리에서 모서리 2개를 제외한 개수^2 * 바닥면을 제외한 면의 개수인 5 * 1면의 최소합

// 모서리
long edges = 4L * (minThree + minTwo);

// 테두리
long borders =  (N-2) * (long)(minTwo * 8 + minOne * 4);

// 안쪽
long inners = (long)(N-2) * (N-2) * 5 * minOne;

// 정답
long answer = edges + borders + inners;

식을 구했으니 이제 면의 최소합을 구하면됩니다.

 

• 3면의 경우
  • 붙어있는 3면은 정육면체 총 6면 중에 서로 마주보지않는 면을 제외한 3면입니다.
  • A =1 ~ F = 6 으로 치환하여 경우의 수를 나열해 보겠습니다. 
    • 1 2 3
    • 1 2 4
    • 1 5 3
    • 1 5 4
    • 6 2 3
    • 6 2 4
    • 6 5 3
    • 6 5 4
  • 위의 경우의 수를 확인해보면 마주보는 면끼리는 같이 있지 않습니다.
  • 1 - 6 / 2 - 5 / 3 - 4 가 서로 마주보기 때문에 각각 작은 면을 구해 3면을 더해주면 됩니다.
• 2면의 경우
  • 한 면을 기준으로 마주보는 면을 제외한 모든 면과 조합할 수 있습니다.
  • 여기서는 최소합을 구해야하기 때문에 위에서 구한 것을 이용합니다.
  • 마주보는 면 3가지 중 작은 경우 2가지를 더합니다.
• 1면의 경우
  • 제일 작은 면을 구합니다.

코드로 보면 더 쉽게 이해할 수 있습니다.

면의 최소합과 공식을 구했으니 코드로 옮겨보겠습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    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());
        
        int[] dice = new int[6];
        
        int sum = 0;
        int max = 0;

        for (int i = 0; i < 6; i++) {
            int num = Integer.parseInt(st.nextToken());

            dice[i] = num;
            
            sum += num;
            max = Math.max(max, num);
        }
        
        if (N == 1) {
            System.out.println(sum - max);
            return;
        }
        
        ArrayList<Integer> minTwoList = new ArrayList<>();

        for (int i = 0; i < 3; i++) {
            minTwoList.add(Math.min(dice[i], dice[5 - i]));
        }
        
        Collections.sort(minTwoList);
        
        int minOne = minTwoList.get(0);
        int minTwo = minTwoList.get(0) + minTwoList.get(1);
        int minThree = minTwoList.get(0) + minTwoList.get(1) + minTwoList.get(2);
        
        // 모서리
        long edges = 4L * (minThree + minTwo);

        // 테두리
        long borders =  (N-2) * (long)(minTwo * 8 + minOne * 4);

        // 안쪽
        long inners = (long)(N-2) * (N-2) * 5 * minOne;

        // 정답
        long answer = edges + borders + inners;

        System.out.println(answer);
    }

}

자바 80ms