백준 온라인 저지, 그리디 / 1041번: 주사위 (파이썬 / 백준 골드문제)

문제

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

주사위는 위와 같이 생겼다. 주사위의 여섯 면에는 수가 쓰여 있다. 위의 전개도를 수가 밖으로 나오게 접는다.

A, B, C, D, E, F에 쓰여 있는 수가 주어진다.

지민이는 현재 동일한 주사위를 N³개 가지고 있다. 이 주사위를 적절히 회전시키고 쌓아서, N×N×N크기의 정육면체를 만들려고 한다. 이 정육면체는 탁자위에 있으므로, 5개의 면만 보인다.

N과 주사위에 쓰여 있는 수가 주어질 때, 보이는 5개의 면에 쓰여 있는 수의 합의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수는 50보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

제한

예제 입력 1

2
1 2 3 4 5 6

예제 출력 1

36

예제 입력 2

3
1 2 3 4 5 6

예제 출력 2

69

예제 입력 3

1000000
50 50 50 50 50 50

예제 출력 3

250000000000000

예제 입력 4

10
1 1 1 1 50 1

예제 출력 4

500

힌트

접근 방법

- N >= 2일 때 N ** 3 크기의 정육면체의 위쪽을 제외한 각 면마다 위의 모서리 두 개의 주사위는 세 면이 드러나고 (N * 3 - 4)개의 주사위는 두 면이 드러난다. 그리고 (N ** 2 - (N * 3 - 2))개의 주사위는 한 면만 드러난다.
- 한 면을 기준으로 위와 같이 주사위의 숫자를 채워넣는다면 반대편도 같은 숫자로 저장할 수 있다.
- 이때 나머지 사이드 면은 가장 위에 위치한 주사위가 2개의 면이 있다는 점만 고려하면 되기에 n - 2개의 주사위가 두 면이 드러나고 나머지는 한 면만 드러나는 것을 고려해 계산하고 그 반대편도 같은 값을 가지기에 전체 값에 곱하기 2를 해준다.
- 이후 위쪽 면은 n ** 2 - (n * 4 - 4)개만큼 가장 작은 숫자를 저장하면 표면에 보이는 가장 작은 숫자를 구할 수 있다.
- 따라서 위의 식을 종합하여 수식으로 나타내면 다음과 같다.
- 세 면 중 가장 작은 수 * 2 * 2 + 두 면 중 가장 작은 수 *((N * 3 - 4) * 2 + (N - 2) * 2) + (한 면 중 가장 작은 수 * ((N ** 2 - (N * 3 - 2)) * 4 + (n ** 2 - (n * 4 - 4)))
- n = 1일 때는 가장 숫자가 큰 것을 제외하고 다른 모든 숫자를 더한 뒤, 출력한다.

코드

# https://www.acmicpc.net/problem/1041
# 접근 방법
# N >= 2일 때 N ** 3 크기의 정육면체의 위쪽을 제외한 각 면마다 위의 모서리 두 개의 주사위는 세 면이 드러나고 (N * 3 - 4)개의 주사위는 두 면이 드러난다. 그리고 (N ** 2 - (N * 3 - 2))개의 주사위는 한 면만 드러난다.
# 한 면을 기준으로 위와 같이 주사위의 숫자를 채워넣는다면 반대편도 같은 숫자로 저장할 수 있다.
# 이때 나머지 사이드 면은 가장 위에 위치한 주사위가 2개의 면이 있다는 점만 고려하면 되기에 n - 2개의 주사위가 두 면이 드러나고 나머지는 한 면만 드러나는 것을 고려해 계산하고 그 반대편도 같은 값을 가지기에 전체 값에 곱하기 2를 해준다.
# 이후 위쪽 면은 n ** 2 - (n * 4 - 4)개만큼 가장 작은 숫자를 저장하면 표면에 보이는 가장 작은 숫자를 구할 수 있다.
# 따라서 위의 식을 종합하여 수식으로 나타내면 다음과 같다.
# 세 면 중 가장 작은 수 * 2 * 2 + 두 면 중 가장 작은 수 *((N * 3 - 4) * 2 + (N - 2) * 2) + (한 면 중 가장 작은 수 * ((N ** 2 - (N * 3 - 2)) * 4 + (n ** 2 - (n * 4 - 4)))
# n = 1일 때는 가장 숫자가 큰 것을 제외하고 다른 모든 숫자를 더한 뒤, 출력한다.

n = int(input())
array = list(map(int, input().split()))
min_value1 = sum(array)
min_value2 = sum(array)
min_value3 = sum(array)
for i in range(6):
    min_value1 = min(min_value1, array[i])
    for j in range(i+1, 6):
        if i + j == 5: # 대척점에 있는 수들간의 합이 불가능하기에 해당 숫자는 제외 
            continue
        min_value2 = min(min_value2, array[i] + array[j])
        for k in range(j+1, 6):
            if i + k == 5 or j + k == 5: 
                continue
            min_value3 = min(min_value3, array[i] + array[j] + array[k])
if n >= 2:
    # 정면과 반대편 면
    result = (min_value3 * 2 + min_value2 * (n * 3 - 4) + min_value1 * ((n ** 2) - (n * 3 - 2))) * 2 
    
    # 나머지 사이드 면
    result += (min_value2 * (n - 2) + min_value1 * (n ** 2 - (n * 3 - 2))) * 2

    # 위쪽 면
    result += min_value1 * (n ** 2 - (n * 4 - 4))

else:
    result = sum(array)- max(array)

print(result)