[백준]1041: 주사위(java)

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

1041번: 주사위

문제

    +---+        
    | 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보다 작거나 같은 자연수이다.

출력

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

예제 입력 1 

2
1 2 3 4 5 6

예제 출력 1 

36

 

---

풀이

옆면(4개)	윗면

N이 4일떄를 기준으로 주사위를 쌓으면 다음과 같이 나타난다.

우리는 이 모양을 통해 다음과 같은 점화식을 도출할 수 있다.

1) 1면만 보이는 경우

5*(N-2)*(N-2) + 4*(N-2)

(N-2)*(N-2)가 옆면 4개 + 윗면 1개에 존재하고

옆면에는 N-2개가 4개 존재한다.

 

2) 2면만 보이는 경우

8*(N-2) + 4

옆면, 윗면으로 봤을때 서로 공유하므로 옆면 기준으로만 생각하면됩니다.

(N-2) * 8 인데 옆면에 바닥면으로 인해 생긴 1개씩 4면이 추가돼 (N-2)*8 + 4가 됩니다.

 

3) 3면이 보이는 경우는 간단하게 4 입니다.

 

이제 문제를 어떤식으로 풀이하였는지 보겠습니다.

두면이든, 세면이든 우리는 인접한면이 어떤 면인지만 알면 됩니다.

즉, 인접하지 않은 면은 단 하나이기에 인접하지 않은 경우만 걸러주면 되겠다고 생각했습니다.

위 그림에서 같은 색은 서로 마주보는 면으로 인접하지 않은 경우입니다.

저는 이 경우를 빠르고 효율적으로 찾고싶어 Map 자료구조를 사용하였습니다.

crossDice = new HashMap<>();
crossDice.put(0, 5);
crossDice.put(1, 4);
crossDice.put(2, 3);
crossDice.put(3, 2);
crossDice.put(4, 1);
crossDice.put(5, 0);

map의 key는 value와 인접할 수 없는 경우입니다.

 

map을 활용하여 두 면의합을 찾는 함수

public static long findMinTwo() {
    long result = Long.MAX_VALUE;

    for(int i=0; i<6; i++) {
        for(int j=0; j<6; j++) {
            if(i==j || crossDice.get(i) == j) continue;
            if(result > arr[i] + arr[j]) {
                result = arr[i]+arr[j];
            }
        }
    }
    return result;
}

- i, j가 면을 모두 탐색합니다.

- 같은 면을 선택한경우는 제외시켜줍니다. (i==j)

- map의 key와 value로 등록돼있는 경우는 제외시켜줍니다. (crossDice.get(i) == j)

- 위 두 조건이 아닌 모든 경우중 최솟값을 반환합니다.

 

세 면의 합을 구하는 함수는 위 함수와 거의 동일하므로 설명을 생략하겠습니다.

 

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class BJ_G5_1041_주사위 {
    static long N;
    static int[] arr;
    static HashMap<Integer, Integer> crossDice;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Long.parseLong(br.readLine());
        arr = new int[6];
        st = new StringTokenizer(br.readLine());
        long min = 50;
        int sum = 0;
        int max = 0;
        for(int i=0; i<6; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            sum+=arr[i];
            if(min > arr[i]) min = arr[i];
            if(max < arr[i]) max = arr[i];
        }

        if(N==1) {
            System.out.printf("%d", sum-max);
            System.exit(0);
        }

        crossDice = new HashMap<>();
        crossDice.put(0, 5);
        crossDice.put(1, 4);
        crossDice.put(2, 3);
        crossDice.put(3, 2);
        crossDice.put(4, 1);
        crossDice.put(5, 0);

        // 한 면을 미리 답에 넣어준다.
        long oneMin = (5*(N-2)*(N-2) + 4*(N-2))*min;
        long twoMin = (8*(N-2)+4)*findMinTwo();
        long threeMin = 4*findMinThree();
        System.out.println(oneMin+twoMin+threeMin);
    }

    public static long findMinTwo() {
        long result = Long.MAX_VALUE;

        for(int i=0; i<6; i++) {
            for(int j=0; j<6; j++) {
                if(i==j || crossDice.get(i) == j) continue;
                if(result > arr[i] + arr[j]) {
                    result = arr[i]+arr[j];
                }
            }
        }
        return result;
    }

    public static long findMinThree() {
        long result = Long.MAX_VALUE;

        for(int i=0; i<6; i++) {
            for(int j=0; j<6; j++) {
                if(i==j || crossDice.get(i) == j) continue;
                for(int k=0; k<6; k++) {
                    if(k==i || k==j || crossDice.get(i) == k || crossDice.get(j) == k) continue;
                    if(result > arr[i] + arr[j] + arr[k]) {
                        result = arr[i]+arr[j]+arr[k];
                    }
                }
            }
        }
        return result;
    }
}

/*
한 면만 보임 = 5*(N-2)*(N-2) + 4*(N-2)
두 면이 보임 = 8*(N-2) + 4
세 면이 보임 = 4개
 */