[백준 1041] 주사위 - JAVA

BOJ Link

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

 

 

풀이 과정

그리디 + 구현 문제이며, 간만의 하드 코딩이였다.

 

1. 한 개의 주사위 구성하기

 

한 개의 주사위에 대해, 문제에서 요구하는 경우는 3가지이다.

그리디 하게 정답을 구성할 수 있으므로, 아래의 값만 사용하여 최종 주사위를 구성한다.

 

주사위의 한 면만 보일 때 (min1)

한 면의  최소값이다.

 

주사위의 두 면만 보일 때 (min2)

인접한 두 면의 최소값이다.

A면과 F면처럼 두 면이 수평한 경우를 제외하고 모든 경우를 구해준다.

 

주사위의 세 면만 보일 때 (min3)

인접한 세 면의 최소값이다. 조합의 응용으로 구할 수 있나 생각했지만, 이는 꽤나 고려해야할 조건이 생긴다.

대신, 하드 코딩으로 i번째 면과 두개의 면이 인접한 경우를 모두 구한 후(6*4가지), 조합이므로 중복한 경우를 빼준다.

가령, A+C+E와 E+C+A는 같다. 총 8개의 경우가 생긴다.

 

2. 최종 주사위 구성하기

 

n=1이라면, 1*1*1=1 주사위에서는 한 주사위의 5면이 보인다. 가장 큰 값을 가진 면을 제외한 것이 정답이다.

 

n=2라면, 2*2*2=8개로 이루어진 주사위의

꼭대기 층에서 3면이 보이는 주사위는 4개 이다.

2층에서 2면이 보이는 주사위는 4개이다.

 

n=3라면, 3*3*3=27개로 이루어진 주사위의

꼭대기 층에서 3면 4개,  2면 4개, 1면 1개이다.

2+3층에서 2면 8개, 1면 8개이다.

나머지 2개의 주사위는 보이지 않는다.

 

이를 바탕으로 점화식을 세우면,

 

꼭대기층

(min3 * 4) + (min2 * (N - 2) * 4) + (min1 * (N - 2) * (N - 2))

나머지층

(min1 * (N - 1) * (N - 2) * 4)) + (min2 * (N - 1) * 4)

라는 공식이 도출된다. 두 값을 더한 것이 N*N*N 크기의 주사위에 대한 정답이다.

 

제출 코드

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

class Main {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] dice = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int A = dice[0], B = dice[1], C = dice[2], D = dice[3], E = dice[4], F = dice[5], dl = 6;

        long min1 = Arrays.stream(dice).min().getAsInt();
        long min2 = Integer.MAX_VALUE;

        // 두 면이 인접한 경우 중 최소 : A-F, B-E, C-D는 인접하지 않는다.
        for (int i = 0; i < dl; i++) {
            int ndice = dice[i];
            if (i != 5 && i != 0)
                min2 = Math.min(min2, Math.min(A, F) + ndice);
            if (i != 4 && i != 1)
                min2 = Math.min(min2, Math.min(B, E) + ndice);
            if (i != 3 && i != 2)
                min2 = Math.min(min2, Math.min(C, D) + ndice);
        }

        long min3 = Integer.MAX_VALUE;

        // 한 주사위의 3면이 모두 인접한 경우 중 최소
        min3 = Math.min(min3, A + B + C);
        min3 = Math.min(min3, A + B + D);
        min3 = Math.min(min3, A + E + C);
        min3 = Math.min(min3, A + E + D);
        min3 = Math.min(min3, B + F + C);
        min3 = Math.min(min3, B + F + D);
        min3 = Math.min(min3, C + F + E);
        min3 = Math.min(min3, D + F + E);

        if (N == 1) {
            System.out.println(Arrays.stream(dice).sum() - Arrays.stream(dice).max().getAsInt());
        } else {
            System.out.println((min3 * 4) + (min2 * (N - 2) * 4) + (min1 * (N - 2) * (N - 2))
                    + ((min1 * (N - 1) * (N - 2) * 4)) + (min2 * 4 * (N - 1)));
        }
    }
}