N에 수에 따른 규칙을 찾아보면
N=1일때는 1,2,3,4,5 면이 보이는 주사위 한개가 놓여지고
N>1일때는
3개 면이 보이는 주사위의 수 : 항상 4개
2개 면 보이는 주사위의 수 (n-1)*4+(n-2)*4 = 4(2n-3) = 8n-12개
1개 면 보이는 주사위의 수 4(n-2)(n-1)+(n-2)^2 = 5n^2 - 16n + 12
가 된다.
따라서 1개 면이 보일때는 정육면체 면중 가장 작은 값이 있는 면이 보여져야 하고
2개 면이 보이는 경우에는 '마주보고 있지 않은' 면 중 합이 가장 작은 두 면이 보여져야 하고
3개 면이 보이는 경우에는 한 모서리를 공유하는 주사위의 세 면의 합이 최소가 되어야 한다. 따라서 마주보는 면 3쌍의 최솟값을 각각 구한 후 더해주면 된다.
여기서 먼저 주의할 점은 오버플로우가 발생할 수 있다는 거다.
계산 과정에서 20억이 넘어갈 수 있으므로 int타입이 아닌 long타입으로 받아 계산해 주었다.
그리고 N==1인 경우는 따로 결과값을 계산해 주어야 한다.
public class Baek_1041 {
static int[] arr = new int[6];
static long m2 = Long.MAX_VALUE;
static long m3 = Long.MAX_VALUE;
static long m1 = Long.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int i = 0;
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
while (st.hasMoreTokens()) {
arr[i] = Integer.parseInt(st.nextToken());
i++;
}
for (int j = 0; j < 5; j++) {
for (int k = j + 1; k < 6; k++) {
if ((j == 0 && k == 5) || (j == 1 && k == 4) || (j == 2 && k == 3)) {
continue;
}
m2 = Math.min(m2, arr[j] + arr[k]);
}
}
m3 = Math.min(arr[0], arr[5]) + Math.min(arr[1], arr[4]) + Math.min(arr[2], arr[3]);
for (int j = 0; j < 6; j++) {
m1 = Math.min(m1, arr[j]);
}
Arrays.sort(arr);
System.out.println(dice(N));
}
static long dice(long N) {
long result3 = 4 * m3;
long result2 = (8 * N - 12) * m2;
long result1 = (5 * N * N - 16 * N + 12) * m1;
long result = N==1?arr[0]+arr[1]+arr[2]+arr[3]+arr[4]:result1+ result2 + result3;
return result;
}
}
'Algorithm' 카테고리의 다른 글
[백준1764]HashSet과 ArrayList의 contains() 시간복잡도 (0) | 2023.07.01 |
---|---|
백준7576 토마토 (0) | 2023.06.11 |
백준 1663 -XYZ 문자열 (0) | 2023.05.03 |
[Java] 이항계수 /백준 1010, 11051 (0) | 2023.05.01 |
[JAVA] DFS,재귀 이해하기/ 백준 2644 촌수계산 (0) | 2023.05.01 |