(Python) - BOJ(1041번) : 주사위

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

1041번: 주사위

 

• 해설 :

                                            +---+        
                                            | D |        
                                        +---+---+---+---+
                                        | E | A | B | F |
                                        +---+---+---+---+
                                            | C |        
                                            +---+

 전개도가 다음과 같은 주사위의 A부터 F까지의 수가 주어지고 이를 N x N x N 개 쌓아서 정육면체를 만든다고 할 때, 

바깥에 드러나는 5개의 면들에 있는 숫자들의 합의 최솟값을 찾는 문제이다.

 

 

 

 

• 풀이 :

수학에 많이 약한 내가 풀기엔 머리가 너무 어지러웠다. 우선, 처음에는 최대값만 안보이는 경우를 선택하는 그리디 방식으로 해결하려고 하였으나 풀면서도 이건 아니다 싶었다. 다른 사람이 푼 코드를 참고하여 구현하였는데

N^3의 정육면체에서 주사위들의 면이 드러나는 경우는 3개의 면이 드러나는 경우 (맨 윗쪽 모서리에 있을 때, ), 두 개의 면이 드러나는 경우 (맨 윗쪽이 아닌 모서리에 있을 때), 1개의 면만 드러나는 경우( 모서리가 아닐 때) 의 3가지이다.

이 경우들에 대해 주사위의 수들 최솟값을 고르는 경우를 선택하여 더해주었다.

 

 

나한텐 정말 어려운 문제였다. 코딩테스트에 나오면 문제 보자마자 일단 패스다

 

 

import sys
input = sys.stdin.readline
 
def twoD(dice):
    j = 5
    ret = []
    for i in range(3):
        ret.append(min(dice[i], dice[j]))
        j -= 1
    ret.sort()
    ret = ret[:2]
    return ret
 
def threeD(dice):
    j = 5
    ret = []
    for i in range(3):
        ret.append(min(dice[i],dice[j]))
        j -= 1
    return ret
 
if __name__ == "__main__":
    n = int(input())
    dice = list(map(int,input().split()))
    td = sum(threeD(dice))
    ta = sum(twoD(dice))
 
    if n == 1 :
        print(sum(dice) - max(dice))
    elif n == 2:
        print((ta*4) + (td*4))
    else:
        print((td*4) + (ta*4*(2*n-3)) +(min(dice)*(4*(n-1)*(n-2)+(n-2)*(n-2))))