BOJ 1041 : 주사위 (Python)

문제

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

1041번: 주사위

 

 

코드

import sys
N = int(sys.stdin.readline())

array = list(map(int, sys.stdin.readline().split()))

one = min(array)

two = 100 # 50 * 2 = 두 면의 최대 합 
three = 150 # 50 * 3 = 세 면의 최대 합

if N == 1: # N==1이라면 총 주사위 숫자 합에서 가장 큰 값을 뺀다.
    print(sum(array)-max(array))
    
else: # N>=2 일 때
    for i in range(6):
        three_list = []
        two_list = []
        for j in range(6):
            if i+j!=5 and i!=j:
                two_list.append([array[i]+array[j],j])
        two_list.sort()
        if two > two_list[0][0]:
            two = two_list[0][0]
        for q in range(6):
            for j in range(len(two_list)):
                if i+q!=5 and two_list[j][1]+q!=5 and i!=q and two_list[j][1]!=q:
                    three_list.append(two_list[j][0]+array[q])
        three_list.sort()
        if three > three_list[0]:
            three = three_list[0]

    print((three*4) + (two*(8*N - 12)) + (one*5*((N-2)**2)) +(one * 4* (N-2)))

 

 

풀이

보이는 5개의 면에 쓰여 있는 수의 합의 최솟값은 다음과 같은 식으로 구할 수 있다.

• 최상단 면의 4개의 꼭짓점에 위치하는 3면을 드러내는 주사위들
• 최하단 면의 4개의 꼭짓점에 위치하는 2면을 드러내는 주사위들
• 바닥에 붙어있는 4개의 변들을 제외하고 나머지 8개의 변에 각각 위치하여 2면을 드러내는 (N-2)개의 주사위들 → 꼭짓점에 위치하는 주사위 2개는 제외
• 바닥에 붙어있는 면을 제외하고 5개의 면에서, 면의 가장자리를 제외하고 내부에 위치하여 1면을 드러내는 주사위들 

모두 다 합쳐서 식으로 나타내면 

 

(3면 * 4) + (2면 * 4) + (2면 * 8 * (N-2)) + (1면 * 5 * (N-2)**2) 

 

이제 최소가 되는 3면 조합, 최소가 되는 2면 조합을 구해서 대입만 하면 된다. → 1면은 주사위 숫자 중 최솟값에 해당함.

 

 

아래는 2면 조합을 구하는 과정이다.

for j in range(6):
            if i+j!=5 and i!=j:
                two_list.append([array[i]+array[j],j])

2면 조합, 3면 조합은 마주 보고 있는 면과 조합될 수는 없기 때문에 인덱스를 합친 값이 5가 되지 않는지 확인한다.

또한 면이 중복되면 안되므로 같은 면이 아닌지도 확인한다.

 

모두 해당하지 않으면 two_list(2면 조합)에 0열에는 두 면의 숫자를 합친 값을, 1열에는 두번째 면의 인덱스 값을 넣는다.  → 3면 조합을 만들 때 마주보고 있지 않는지 확인하기 위해 사용하는 인덱스 값임

 

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

A B C D E F 는 인덱스 번호가 차례대로 0, 1, 2, 3, 4, 5 이고 {A-F}, {B-E}, {C-D} 는 마주보고 있으므로 제외해야 한다.

이를 인덱스 번호로 바꾸면 {0-5}, {1-4}, {2-3} 이므로 i+j!=5 인지 확인하는 과정을 거치는 것이다. 

 

 

아래는 3면 조합을 구하는 과정이다. 

for q in range(6):
            for j in range(len(two_list)):
                if i+q!=5 and two_list[j][1]+q!=5 and i!=q and two_list[j][1]!=q:
                    three_list.append(two_list[j][0]+array[q])

위에서 구한 two_list (2면 조합) 를 이용해서 이미 조합된 2면과 모두 마주보고 있지 않은 면을 추가하여 3면 조합을 만든다. 

 

two_list (2면 조합) 과 three_list(3면 조합) 둘 다 조합을 모두 구한 뒤에 정렬을 하면 가장 좌측의 값이 최소가 되는 2면 조합의 최솟값, 최소가 되는 3면 조합의 최솟값이 된다.

 

 

이렇게 구한 최솟값을 위의 식에 대입하면 답이 나온다.