백준 1041 주사위

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

정육면체인 주사위가 있고, 해당 주사위의 각 위치에 해당하는 숫자가 주어진다.

이 주사위를 N N N의 영역에 쌓아 만들어진 정육면체의 5면에 쓰여있는 수의 합의 최솟값을 구하는 문제이다.

딱히 어려운 알고리즘이나 아이디어가 필요한 것도 아니고 풀다 보면 BigInteger를 다뤄 봤냐 물어보는 문제같다고 느꼈다.

N * N * N의 정육면체가 있다면, 정육면체의 각 주사위들은 1개에서 3개의 면이 노출된다.

정육면체에서 3면이 노출되는 위치는

위처럼 상단의 꼭짓점 4개이고

2면이 노출되는 위치는

꼭짓점을 제외한 빨간 선 쪽의 주사위들이다.

마지막으로 1면이 노출되는 위치는

위의 빨간 면쪽에 해당하는 주사위들이다.

문제에 나온 주사위의 전개도를 토대로 만들수 있는 합의 조합은 다음과 같다.

1. 주사위 1면의 합 - 6개의 값 중 최솟값을 사용한다.

2. 주사위 2면의 합 - 붙어 있는 면인 AB, AC, AD, AE, BC, BD, BF, CE, CF, DE, DF, EF 들 중 합이 최소인 값을 사용한다.

3. 주사위 3면의 합 - 3면이 감싸며 붙어 있는 ABC, ABD, ACE, ADE, BCF, BDF, CEF, DEF 들 중 합이 최소인 값을 사용한다.

위 방법을 이용해 구한 밖으로 노출된 면의 최소합으로 정육면체의 빨간 부분을 채우면 된다

import java.math.BigInteger
import java.util.*

lateinit var num: List<Int>

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val N = readLine().toInt()

    num = readLine().split(' ').map{it.toInt()}

    if(N == 1){
        print(num.sum() - num.maxOrNull()!!)
        return@with
    }

    var answer = BigInteger.ZERO

    val oneSide = getMinOneSide()
    val twoSide = getMinTwoSide()
    val threeSide = getMinThreeSide()

    // 위쪽 4개 꼭짓점
    answer += threeSide.multiply(BigInteger("4"))

    // 2면씩 보이는 모서리들
    // 8 * twoSide * (N - 2) + 4 * twoSide = (8 * N - 12) * twoSide
    answer += twoSide.multiply(BigInteger("${8 * N - 12}"))

    // 1면씩 보이는 중앙 + 바닥부분
    // 5 * (N - 2) * (N - 2) * oneSide + 4 * (N - 2) * oneSide = (N - 2) * (5N - 6) * oneSide
    answer += BigInteger("${N - 2}").multiply(BigInteger("${5 * N - 6}")).multiply(BigInteger("$oneSide"))

    print(answer)
}

fun getMinOneSide() = num.minOrNull()!!

fun getMinTwoSide(): BigInteger{
    // AB, AC, AD, AE, BC, BD, BF, CE, CF, DE, DF, EF
    val l1 = listOf(0, 0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4)
    val l2 = listOf(1, 2, 3, 4, 2, 3, 5, 4, 5, 4, 5, 5)

    var min = Int.MAX_VALUE
    for(i in l1.indices){
        val sum = num[l1[i]] + num[l2[i]]
        if(sum < min) min = sum
    }
    return BigInteger(min.toString())
}

fun getMinThreeSide(): BigInteger{
    // ABC, ABD, ACE, ADE, BCF, BDF, CEF, DEF
    val l1 = listOf(0, 0, 0, 0, 1, 1, 2, 3)
    val l2 = listOf(1, 1, 2, 3, 2, 3, 4, 4)
    val l3 = listOf(2, 3, 4, 4, 5, 5, 5, 5)

    var min = Int.MAX_VALUE
    for(i in l1.indices){
        val sum = num[l1[i]] + num[l2[i]] + num[l3[i]]
        if(sum < min) min = sum
    }
    return BigInteger(min.toString())
}

참고로 N이 1,000,000 이하의 자연수이므로 1 x 1 x 1 정육면체도 가능하다.

그럴 경우 가장 큰 숫자를 바닥으로 놓고 남은 5면의 합을 출력한다.