[백준] 1041 - 주사위

1. 문제

1041번: 주사위

2. 개요

그리디 문제.

각 면에 숫자가 쓰여진 주사위로 만든 정육면체의 보이는 면의 모든 수의 합의 최솟값을 구하면 된다.

정육면체로 정육면체를 만들 때,

n = 1 이면 한 정육면체의 5개 면이 보이고

n = 2 면 2층의 정육면체는 각각 3개의 면이 보이고, 1층의 정육면체는 각각 2개 면이 보인다.

n ≥ 3 이면, 최상층 3층의 꼭짓점의 정육면체는 3면, 이를 제외한 모서리의 정육면체는 2면, 나머지는 1개 면이 보이게 된다.

수식으로 나타내면 다음과 같다.

n ≥ 2일때,

3면 보이는 정육면체는 4개,

2면이 보이는 정육면체는 4(n-2) + 4(n-1) = 4(2n-3) = 8n-12

1면이 보이는 정육면체는,

총 면은 5n^2 이고 다면이 보이는 정육면체의 면의 갯수들을 빼 준 경우이므로,

5n^2 - 4 * 3 - (8n - 12) * 2 = 5n^2 - 16n - 36 이다.

이제 각각의 경우에 나올 수 있는 최솟값들을 구해서 더해주면 된다.

1면은 숫자들의 최솟값의 경우가 될 것이고,

2면인 경우에는 연결되어있는 두 면끼리 합친 값의 최솟값,

3면인 경우에는 2면 최솟값 + 윗면 최솟값이 된다.

3. 코드 및 추가 설명

import sys

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

if N == 1:
    print(sum(nums) - max(nums))

else:
    nums[4], nums[5] = nums[5], nums[4]
    n1 = min(nums)
    n3 = min(nums[2], nums[3]) + nums[4] + nums[1]
    for i in range(1, -2, -1):
        n3 = min(n3, min(nums[2], nums[3]) + nums[i] + nums[i-1])

    n2 = nums[4] + nums[1]
    for i in range(1, -3, -1):
        n2 = min(n2, min(nums[2], nums[3]) + nums[i], nums[i] + nums[i-1])

    ans = 4 * n3 + (8 * N - 12) * n2 + (5 * (N ** 2) - 12 - (8 * N - 12) * 2) * n1
    print(ans)

리스트와 실제 주사위의 연결을 맞추기 위해 4,5 인덱스를 5,4로 변경하고

for 문도 연결 면의 합을 구하기 위해 역을 돌렸다.

근데 이러면 B+F를 돌지 않기 때문에 2면, 3면인 n2, n3의 초기값으로 세팅했다.