11회차 스터디 준비

주제 : 그리디 알고리즘

 

내 문제 : 주사위_1041

1041번: 주사위

 

 

N=1일 때 =>

보이는 면은 바닥면을 제외한 다섯 면이므로

바닥면에 가장 작은 수를 위치 시킨다.

---

N=2일 때 =>

세 면이 보이는 주사위가 4개(위쪽 각 모서리)

두 면이 보이는 주사위가 4개(아래 쪽각 모서리)

---

N=3일 때 =>

세 면이 보이는 주사위가 4개(위쪽 각 모서리) 

 

---

두 면이 보이는 주사위가 8개 = (N-2)*8

+ 4개(아래 쪽각 모서리) 

총 12개

---

한 면이 보이는 주사위가 5개 (N-1)^2 * 5

+ 4개 (N-2)*4

총 9개

 

 

규칙을 보면

N이 1인 경우

하나의 면을 제외하고 다섯 면이 보인다. 이때 가장 작은 값을 구하면 된다.

- 다섯 면이 보이는 경우

 

N이 2이상인 경우

각 주사위들의 보이는 면의 갯수를 구해서 비교하여야 한다.

보이는 면의 종류는

- 한 면이 보이는 경우

- 두 면이 보이는 경우

- 세 면이 보이는 경우

가 있다.

 

한 면이 보이는 주사위의 수는

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

두 면이 보이는 주사위의 수는

((N - 2) * 8) + 4

세 면이 보이는 주사위의 수는

4 

이다.

 

이제 각 주사위에서 두 면이 보일 때 최소값, 세 면이 보일 때 최소값들을 각 갯수에 곱하여

최소 값을 구하면 된다.

---

코드로 확인 해보자.

 

arr[ i ]에는 

connection[ i ][ j ]에는 주사위의 i번 째 면에 연결되어있는 네 가지 면의 번호를 등록한다.

나는 구해야 하는 면의 갯수를 구하는 함수를 각각 구현했다.

필요한 경우는 다섯 면이 보이는 경우, 한 면, 두 면, 세 면이 보이는 경우 총 4개이다.

 

두 면의 합을 구하는 것은 

arr[ i ] 에 연결되어있는 면 중 하나를 더하면 되고

arr[i] + arr[connection[i][j]]

세 면의 합을 구하는 것은

arr[ i ] 에 연결되어있는 면 중 하나를 더하고 그곳에 연결되어있는 면을 하나 더하면 된다.

arr[i] + arr[connection[i][j]] + arr[connection[i][j+1]]

최솟값을 구해야하므로 주사위의 각면을 대입해보면서 최솟값을 갱신하면 된다.

---

코드작성

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {
    static int[] arr;
    static int[][] connection;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        connection = new int[6][];
        connection[0] = new int[]{1, 2, 4, 3};
        connection[1] = new int[]{0, 2, 5, 3};
        connection[2] = new int[]{0, 1, 5, 4};
        connection[3] = new int[]{0, 1, 5, 4};
        connection[4] = new int[]{0, 2, 5, 3};
        connection[5] = new int[]{1, 2, 4, 3};

        int N = Integer.parseInt(br.readLine());
        String[] str = br.readLine().split(" ");
        arr = new int[6];

        for (int i = 0; i < 6; i++) {
            arr[i] = Integer.parseInt(str[i]);
        }

        if (N == 1) {
            System.out.println(getFive());
        } else {
            long one =//1면 갯수
                    getOne() * (long) (N - 2) * 4
                            + getOne() * (long) Math.pow((N - 2), 2) * 5;
            //2면 갯수
            long two = getTwo() * (long) ((N - 2) * 4 * 2)
                    + getTwo() * 4;
            //3면 갯수
            long three = getThree() * 4;
            System.out.println(
                    one + two + three
            );
        }

    }

    static public long getFive() {
        long max = 0;
        long sum = 0;
        for (int i = 0; i < 6; i++) {
            max = Math.max(max, arr[i]);
            sum += arr[i];
        }
        return sum - max;
    }

    static public long getTwo() {
        long min = arr[0] + arr[connection[0][0]];
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 4; j++) {
                min = Math.min(min, arr[i] + arr[connection[i][j]]);
            }
        }
        return min;
    }

    static public long getThree() {
        long min = arr[0] + arr[connection[0][0]] + arr[connection[0][1]];
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 4; j++) {
                int second = connection[i][j];
                int third;
                if (j == 3) {
                    third = connection[i][0];
                } else {
                    third = connection[i][j + 1];
                }
                min = Math.min(min, arr[i] + arr[second] + arr[third]);
            }
        }
        return min;
    }

    static public long getOne() {
        long min = arr[0];
        for (int i = 0; i < 6; i++) {
            min = Math.min(min, arr[i]);
        }
        return min;
    }

}