[파이썬/python] 백준 - 1041 주사위

문제

https://www.acmicpc.net/problem/1041

---

문제 설명

1. 주사위의 전개도의 각 면에는 수가 쓰여져 있다.(A,B,C,D,E,F)
2. 동일한 주사위를 $N^3$개 가지고 있을 때 적절하게 회전하고 쌓아서 $N^3$크기의 정육면체를 만들려고 한다.
   1. 이 때 정육면체는 탁자위에 있으므로 5개의 면만 보인다.
3. N과 주사위의 수가 주어졌을 때 5개의 면에 쓰여 있는 수의 합의 최솟값을 출력해라.

 

---

풀이

문제를 처음 봤을 때는 단순하게 접근했다.

보이는 면은 총 5개, 그중 대칭되는 면 2개, 2개 윗면 1개로 구성되어 있기 때문에 주사위를 배치할 수 있는 모든 경우의 수를 구해서 그중 가장 합이 낮은 숫자를 선택하기로 했다.

 

2x2x2 정육면체 그림으로 예시를 들어보자.(그림은 알지오매스라는 사이트를 이용했다.) 

처음 접근한 방식은 다음과 같다.

결국에는 하나의 모서리를 공유하는 세 면을 구성할 수 있는 경우의 수 중에서 가장 낮은 수 3개인 경우를 찾아서 위와 같이 배치하게 되면 최솟값이 될 것이라고 생각했다. 실제로 $2^3$ 정육면체에서는 해당 경우가 가능했다.

 

여기서 하나의 모서리를 공유하는 세 면을 구성할 수 있는 경우의 수는 어떻게 구할까?

 

 

구하는 방법은 단순하다.

문제에서 주어진 정육면체 도면을 기준으로 위 아랫면을 잡고 양옆 4개의 면을 돌려서 구성하면 된다. 이를 구해보면 다음과 같다.

 

1. B, C, (A or F)

2. C, E, (A or F)

3. D, E, (A or F)

4. B, D, (A or F)

총 8가지의 경우의 수가 나온다.

 

이를 문제에서 입력받는 순서에 따라 인덱스로 전환해서 선언해두었다.

d = [
    [1,2,0],[1,2,5],
    [1,3,0],[1,3,5],
    [3,4,0],[3,4,5],
    [2,4,0],[2,4,5]]

 

8가지의 경우의 수를 전부 넣어가며 나올 수 있는 경우의 수를 전부 찾고, 합이 가장 작은 조합을 찾는다.

그 후 각 숫자의 크기별로 면에 대입하기 위해 해당 조합을 오름차순으로 정렬했다.

 

-> (1, 2, 3)이라는 조합이 뽑혔다면 1과 2는 2개의 면이 필요한 사이드 면에, 가장 큰 3이라는 숫자는 면이 1개인 윗 면에 들어가게 하기 위함이다.

 

공식은 다음과 같다.

Side 1 = $(n^2 * C [0])*2$

Side 2 = $(n^2 * C [1])*2$

Top = $n^2*C [2]$

 

하지만 n이 2보다 클 경우에는 예외가 발생하게 된다.

n이 4일 경우의 그림을 통해 확인해 보겠다.

 

 

n이 2일 경우에는 빨간색 삼각형 즉 3개의 면이 붙어있는 경우의 수만 존재했다.

하지만 2보다 클 때에는 총 3개의 경우의 수가 존재한다. (3개의 면, 2개의 면, 1개의 면)

 

이걸 인지한 상태에서 위에서 찾은 가장 작은 3개의 수를 어떻게 배치하면 좋을지 고민해 보자.

 

사전에 찾은 가장 작은 조합을 C배열이라고 하겠다. ex) C = [1,2,3]

 

그럼 가장 작은 숫자가 들어가야 하는 사이드 면부터 채워보면

이처럼 모든 면을 1로 채울 수 있다. 가장 작은 수이기 때문에 어떤 숫자가 들어갈지 고려할 필요가 없다.

따라서 이전과 동일하게  $(n^2 * C [0])*2$ 수식을 통해 계산한다.

 

이제 두 번째 숫자가 들어갈 사이드 면을 채워보자.

두 번째 숫자가 들어갈 사이드 면에는 1개의 눈금만 보이는 초록 구간과 2개의 면이 보이는 파란 구간이 존재한다.

1개의 면이 보이는 초록 구간에는 가장 낮은 숫자를 배치할 수 있고

2개의 면이 보이는 파란 구간에는 낮은 숫자부터 순차적으로 1과 2를 배치할 수 있다.

이제 남은 구간도 마찬가지다 현재 넣을 수 있는 가장 낮은 숫자를 배치하면 된다.

 

이로써 사이드면이 전부 채워졌다. 이제 가장 윗 면을 채워보자.

윗면도 마찬가지로 가운데 1개의 면만 보이는 구간에는 1을 배치하고 나머지 모서리에 가장 큰 숫자인 3을 배치했다.

 

전부 배치하고 보면 이제 규칙이 보이기 시작한다.

n이 2보다 큰 경우에는 어떤 숫자가 들어와도 위와 같은 모양을 어기지 않고 배치가 가능해진다.

 

따라서 각 면에 대한 눈금의 합을 다음과 같이 나타낼 수 있다.

Side 1 = $2*(n^2 * C [0])$ 

Side 2 = $(n*2)*C [1] + n*(n-2)*C [0]$

Top = $4*C [2] + 4*(n-2)*C [1] + ((n-2)^2)*C [0]$

 

나는 이 문제를 아래처럼 3개의 경우로 분리해서 풀었다.

1. n = 1일 때 = 가장 큰 눈금을 제외한 합

2. n = 2일 때 

3. n > 2일 때

 

정육면체를 만들기 위해 사용할 세 개의 눈금을 찾는 것, 정육면체를 구성할 때 보이는 면의 수에 따라 그리디 하게 낮은 눈금부터 채우는 것이 이 문제의 핵심이었다고 생각한다.

 

정답 비율이 29%인 것 치고는 그리디에 취약한 나에게는 좀 더 직관적으로 다가와서 쉽게 풀 수 있었던 것 같다.

---

코드

import sys
input = sys.stdin.readline

d = [
    [1,2,0],[1,2,5],
    [1,3,0],[1,3,5],
    [3,4,0],[3,4,5],
    [2,4,0],[2,4,5]]

n = int(input())
arr = list(map(int,input().split()))
if n == 1:
    print(sum(sorted(arr)[:5]))
    exit()

comb = []

for i,j,k in d:
    comb.append([arr[i],arr[j],arr[k]])

comb.sort(key = lambda x: sum(x))
C = sorted(comb[0])

if n == 2:
    res = (n**2)*((C[0]+C[1])*2 + C[2])
else:
    res = 2*(n**2)*C[0] + 2*(2*n*C[1] + (n-2)*n*C[0]) + 4*C[2]+ 4*(n-2)*C[1] + C[0]*((n-2)**2)
    

print(res)

---

시간복잡도

• N은 최악의 경우 $10^6$이다.
• 이 문제는 단순 수식으로 풀이가 가능하기 때문에 정렬할 때 $O(1)$ (실제로는 $nlogn$ 이지만 매우 낮은 수의 정렬이기 때문에) 정도의 시간복잡도를 가질 것으로 보인다.