[BOJ/Python] 1041_주사위
문제 출처:https://www.acmicpc.net/problem/1041
1041번: 주사위
첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수
www.acmicpc.net
문제
+---+
| D |
+---+---+---+---+
| E | A | B | F |
+---+---+---+---+
| C |
+---+
주사위는 위와 같이 생겼다. 주사위의 여섯 면에는 수가 쓰여 있다. 위의 전개도를 수가 밖으로 나오게 접는다.
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보다 작거나 같은 자연수이다.
출력
첫째 줄에 문제의 정답을 출력한다.
예제 입력 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에 대하여 N×N×N 크기의 정육면체를 N이 1인 경우부터 차근차근 접근해나가면 규칙을 발견할 수 있다.
우선 N이 1인 경우이다.
N=1인 경우는 바닥에 한 면을 제외하고 나머지 5면이 모두 보인다.
따라서 이 경우 보이는 면의 최솟값은 (주사위의 모든 눈금의 합) - (가장 큰 눈금)이 된다.
(가장 큰 눈금이 바닥면에 존재하는 경우이다.)
N=2라면 2×2×2의 정육면체 모양이 된다.
이 경우 면이 3개 보이는 부분과 면이 2개 보이는 부분으로 나눌 수 있다.
노란색 주사위의 경우, 면이 3개 보이는 부분이다.
초록색 주사위의 경우, 면이 2개 보이는 부분이다.
이제 N=3인 경우를 살펴보면 다음과 같다.
N=3인 경우, 마찬가지로 노란색 주사위의 경우 3개의 면이 보이는 부분이다.
여기서 잘 생각해보면, 3개의 면이 보이는 부분은 주사위의 제일 윗부분의 네 모퉁이인 것을 알 수 있다.
이것은 N이 아무리 증가하더라도 변하지 않게 된다. (제일 윗부분의 모퉁이는 네 부분밖에 없기 때문이다.)
이어서 녹색 주사위의 경우 2개의 면이 보이는 부분이다.
이 또한 잘 생각해보면, 맨 윗부분의 경우 모서리에서 네 모퉁이를 뺀 나머지 부분임을 알 수 있다.
그리고 아래 부분에서는 네 모퉁이 부분들이 2개의 면이 보임을 알 수 있다.
나머지 파란색 주사위는 1개의 면이 보이는 부분이다.
마지막으로 N=4일때를 확인하고, 수식으로 정리해 보자.
- 맨 윗부분
- 3개의 면 -> 4개 (네 모퉁이)
- 2개의 면 -> 4 * (N-2) 개 (모퉁이를 제외한 나머지 모서리 부분)
- 1개의 면 -> (N-2)**2 개 (맨 윗부분에서 파란색 주사위의 경우, 1->4->9->16의 순으로 늘어간다.)
- 아랫부분 (맨 윗부분을 제외한 N-1개의 부분)
- 2개의 면 -> 4개 (네 모퉁이)
- 1개의 면 -> 4 * (N-2) 개 (모퉁이를 제외한 나머지 모서리 부분)
윗부분과 아랫부분을 합치게 되면 다음과 같은 결론을 내릴 수 있다.
- 3개의 면 -> 4개
- 2개의 면 -> 4 * (2N-3) 개
- 1개의 면 -> (N-2)*(5N-6) 개
만들어진 정육면체의 다섯 면이 최소가 되려면, 각각의 면들의 눈금의 합이 최소가 되어야 한다.
따라서 1개의 면, 2개의 면, 3개의 면에 대하여 최소인 경우를 구해야 한다.
+---+
| D |
+---+---+---+---+
| E | A | B | F |
+---+---+---+---+
| C |
+---+ 1개의 면일 경우, 주사위의 눈금 중 가장 작은 값을 구하면 된다.
이제 2개의 면일 경우를 생각해 보자.
만약 A를 포함한 2개의 면을 만들게 되면, (A, B), (A, C), (A, D), (A, E) 총 4가지 경우가 있다.
즉, A와 F는 평행한 관계이므로 2개의 면을 만들 수 없다. 2개의 면을 고를 때, 평행하지 않은 두 주사위의 눈금을 선택하기만 하면 되므로, 이제 최솟값을 구해보자.
평행한 두 눈금은 선택할 수 없으므로 평행한 눈금들 중 작은 값을 구하고, 구한 3개의 값 중 작은 2개의 값을 더하면 된다.
다시 말해, min(A, F) , min(B, E) , min(C, D)을 구하여 이 중 작은 값 2개를 더하면 된다.
3개의 면일 경우, 마찬가지로 모퉁이에 들어가야 하므로, ACF와 같은 경우는 선택할 수 없다.
즉 여기서도 평행하지 않은 3개의 눈금을 선택해야 하고, 눈금의 합이 최소가 돼야 하므로, min(A, F) + min(B, E) + min(C,D) 을 구하면 된다.
코드는 다음과 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
import sys
n = int(sys.stdin.readline())
dice = list(map(int,sys.stdin.readline().split()))
result = 0
if n==1:
result = sum(dice) - max(dice)
else:
one_face = min(dice)
three_face = min(dice[0],dice[5])+min(dice[1],dice[4])+min(dice[2],dice[3])
two_face = three_face - max(min(dice[0],dice[5]),min(dice[1],dice[4]),min(dice[2],dice[3]))
result+=4*three_face
result+=4*(2*n-3)*two_face
result+=(n-2)*(5*n-6)*one_face
print(result)
|
cs |
- 두 개의 면이 보이는 경우 세 개의 면이 보이는 경우가 min(A, F) + min(B, E) + min(C,D)이므로, 여기서 가장 큰 min(평행한 두 눈금)을 빼 주었다.
- 즉 min(A,F) , min(B,E) , min(C, D)에서 작은 두 개의 값을 구하는 대신, 세 값을 더한 값(세 개의 면이 보이는 경우)에서 가장 큰 값을 빼 주었다.