파이썬 그리디 알고리즘 백준 1041 주사위

문제

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

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

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

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

입력

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

출력

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

풀이

이 문제는 처음에 이해하기 어려웠는데 N^3개의 주사위로 NxNxN의 정육면체를 만들어

총 6면 중 밑면을 제외한 5면에서 보이는 주사위 수 합의 최솟값을 구하는 문제이다.

위 상황의 문제에서 주사위의 면은 1면만 보이거나 2면이 보이거나, 3면이 보이는 경우 밖에 없다.

또한 각 면이 보이는 개수는 정해져 있다.

1면이 보이는 개수는 (n-2)*(n-2) + 4*(n-1)*(n-2) 개,

2면이 보이는 개수는 4*(n-2) + 4*(n-1) 개,

3면이 보이는 개수는 정육면체의 각 꼭짓점으로 4개다.
이제 각 면의 수가 최소가 되도록 보여주면 되는데 주사위 특성상 마주보는 면을 제외하고 모든 면이 인접해있다.

따라서 A,B,C,D,E,F를 사용자에게 입력받았을 때

0과5, 1과4, 2와3중 최소 값을 리스트에 저장하고

1면, 2면, 3면의 경우에 따라 더 작은 것부터 더해서 사용하면 된다.

 

각 면의 개수와 그 면을 사용할 때 최솟값을 구했으니, 전체 정육면체에 보여지는 수의 합은

그 두 값을 곱해서 더해주기만 하면 된다.

 

import sys
n = int(sys.stdin.readline().rstrip("\n"))
nums = list(map(int, sys.stdin.readline().rstrip("\n").split()))
sum=0
sumLists=[]
if(n==1):
    nums = sorted(nums)
    for i in range(0,5):
        sum+=nums[i]
else:
    sumLists.append(min(nums[0],nums[5]))
    sumLists.append(min(nums[1],nums[4]))
    sumLists.append(min(nums[2],nums[3]))
    sumLists = sorted(sumLists)

    #1,2,3면이 보여질때 주사위 최소값
    min1 = sumLists[0]
    min2 = sumLists[0] + sumLists[1]
    min3 = sumLists[0] + sumLists[1] + sumLists[2]

    #1,2,3면이 보여지는 주사위 개수
    n1 = (n-2)*(n-2) + 4*(n-1)*(n-2)
    n2 = 4*(n-2) + 4*(n-1)
    n3 = 4

    sum += n1 * min1
    sum += n2 * min2
    sum += n3 * min3

print(sum)