[알고리즘] 주사위
난이도
Gold 5
문제
+---+
| D |
+---+---+---+---+
| E | A | B | F |
+---+---+---+---+
| C |
+---+
주사위는 위와 같이 생겼다. 주사위의 여섯 면에는 수가 쓰여 있다. 위의 전개도를 수가 밖으로 나오게 접는다.
A, B, C, D, E, F에 쓰여 있는 수가 주어진다.
지민이는 현재 동일한 주사위를 N3개 가지고 있다. 이 주사위를 적절히 회전시키고 쌓아서, N×N×N크기의 정육면체를 만들려고 한다. 이 정육면체는 탁자위에 있으므로, 5개의 면만 보인다.
N과 주사위에 쓰여 있는 수가 주어질 때, 보이는 5개의 면에 쓰여 있는 수의 합의 최솟값을 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수는 50보다 작거나 같은 자연수이다.
출력
첫째 줄에 문제의 정답을 출력한다.
예제 입력
2
1 2 3 4 5 6
예제 출력
36
해설 및 후기
느낌상 그리디보다는 구현에 가까웠다. 우선 예제의 답을 도출해내기 위해 그려서 생각해 보았다.
그리다보니 규칙을 찾을 수 있었다. 사용하는 조각은 총 세개로, 한 면이 최소이거나, 인접한 두 면의 합이 최소이거나, ㄱ 혹은 ㄴ 모양으로 인접한 세 면의 합이 최소인 조각이다. 좌우나 상하가 달라 위치마다 상이할 것 같지만, 돌려서 붙이면 되므로 각 조각을 몇개 사용하는지만 확인하면 된다.
우선 각 조각의 최소를 찾아야한다. itertools등을 사용해야 하나 생각했지만, 주사위의 면이 6개인것은 불변이므로 하드하게 구할 수 있었다. 특히 세 면의 합의 조각을 구하는 경우 각 면이 등장하는 횟수가 4번씩이라는 나름의 꿀팁도 생각해낼 수 있었다.
그렇게 구한 후, 각 조각이 등장하는 횟수를 수식화한다. 3면이 등장하는 경우는 n>1 인 케이스에서 4번으로 고정이다. (꼭대기에 위치한 각 모서리)
다음으로 2면이 등장하는 경우는 꼭대기를 제외한 모든 모서리와, n>2인 경우에서 꼭대기의 끝 부분이다. 즉 (n-2) * 4 + (n-1) * 4
마지막으로 한 면이 등장하는 경우는 n>2에서 각 면의 가운데에 위치하는 면들과, 기둥을 형성하는 면들의 밑부분이다. 즉 (n-2) * (n-2) * 5 + (n-2) * 4
그러면 이 값들을 각 조각들의 값과 곱해 답을 얻을 수 있다. 물론 n=1인 경우는 따로 처리한다.
제출 코드
n = int(input())
nums = list(map(int,input().split()))
if(n==1):
print(sum(nums)-max(nums))
exit()
m1 = min(nums)
m2 = min([nums[0]+nums[1],nums[0]+nums[2],nums[0]+nums[3],nums[0]+nums[4],
nums[1]+nums[2],nums[1]+nums[3],nums[1]+nums[5],
nums[2]+nums[4],nums[2]+nums[5],
nums[3]+nums[4],nums[3]+nums[5],
nums[4]+nums[5],
])
m3 = min([nums[0]+nums[1]+nums[2],nums[0]+nums[1]+nums[3],nums[0]+nums[2]+nums[4],nums[0]+nums[3]+nums[4],
nums[1]+nums[2]+nums[5],nums[1]+nums[3]+nums[5],
nums[2]+nums[4]+nums[5],
nums[3]+nums[4]+nums[5],
])
cnt = 0
cnt += m2 * ((n-1)*4 + (n-2)*4)
cnt += m3 * 4
cnt += m1 * ((n-2)*4 + (n-2)*(n-2)*5)
print(cnt)