문제:
주사위는 위와 같이 생겼다. 주사위의 여섯 면에는 수가 쓰여 있다. 위의 전개도를 수가 밖으로 나오게 접는다.
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*N*N 크기의 정육면체를 만들게 되면, 밖으로 노출되는 면이 가장 많은 경우는 3개인 면인 경우이다. 정육면체에서 3개의 면 주사위의 개수, 2개의 면 주사위의 개수, 1개의 면 주사위의 개수는 N에 따라서 달라지게 된다.
1. 3개의 면 주사위의 개수는 항상 위쪽 면의 꼭짓점에서만 나타나므로 N과 상관없이 4번만 등장하게 된다.
2. 2개의 면이 나타나는 주사위의 개수는 모서리에서만 나타나게 된다. 이 때 위쪽 면에서는 꼭짓점에서 이미 사용한 주사위가 있으므로 이를 제외해주고 계산해줘야 한다. 따라서 (N-1)*4+(N-2)*4개가 존재한다.
3. 1개의 면이 나타나는 주사위는 ((N-2)^2)*5+(N-2)*4 개 있다.
주사위는 위 그림에서 나타나는 것처럼 전개도를 따라서 접게 되므로, 모든 숫자 중에서 가장 작은 3개(혹은 2개)를 골라서 최솟값을 구하면 안된다. A에 있는 숫자는 F와 만날 수 없기 때문이다. 따라서 나타날 수 있는 3개인 경우는 [(0,1,2),(0,1,3),(0,2,4),(0,3,4),(1,2,5),(1,3,5),(2,4,5),(3,4,5)]와 같기 때문에 이 중에서 가장 작은 값을 가지는 경우를 찾도록 하고, 2개인 경우는 서로 반대 면에 있는 숫자만 피하면 되므로, 이를 제외하고 계산하도록 한다.
N이 1인 경우는 위에서 구한 케이스 구분이 필요없기 때문에 따로 처리하도록 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
import copy
def threemin(numbers):
candidate = [(0,1,2),(0,1,3),(0,2,4),(0,3,4),(1,2,5),(1,3,5),(2,4,5),(3,4,5)]
answer = sum(numbers)
for c in candidate:
temp = 0
for idx in c:
temp +=numbers[idx]
answer = min(answer,temp)
return answer
def twomin(numbers):
answer = sum(numbers)
for i in range(len(numbers)):
for j in range(i+1,len(numbers)):
temp = 0
if i+j==5:
continue
else:
temp += (numbers[i]+numbers[j])
answer = min(temp,answer)
return answer
N = int(input())
numbers = list(map(int,input().split()))
answer = 0
if N==1:
answer = sum(numbers)-max(numbers)
else:
three = threemin(numbers)
two = twomin(numbers)
answer += three*4
answer += two*(N-1)*4+two*(N-2)*4
answer += min(numbers)*(N-2)*(N-2)*5+min(numbers)*(N-2)*4
print(answer)
|
cs |
문제링크:
1041번: 주사위
첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수
www.acmicpc.net
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]7562. 나이트의 이동 (0) | 2020.11.19 |
|---|---|
| [BOJ]1992. 쿼드트리 (0) | 2020.11.17 |
| [BOJ]1059. 수2 (0) | 2020.11.10 |
| [BOJ]10775. 공항 (0) | 2020.10.29 |
| [BOJ]1786. 찾기 (0) | 2020.10.27 |