[BOJ 1041, Python 3] 주사위

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

1041번: 주사위

제출할 떄마다 코드를 하나씩 빼먹어서 엄청 나게 틀린 문제...

 

풀이

• 면 3개가 보이는 곳은 4개
• 면 2개가 보이는 곳은 4 * (N - 2) + 4 * (N - 1)개
• 면 1개가 보이는 곳은 (N - 2) * (N - 2) + 4 * (N - 1) * (N - 2)개

여기까지는 바로 구하실 수 있습니다.

 

이제 면을 선택해야하는데 면 2개의 경우에는 인접한 두 면을 선택하면 되는 것이고, 면 3개의 경우에는 한 꼭짓점을 공유하는 3면을 선택해야 하는 것을 알 수 있습니다. 단순히 오름차순 정렬을 하여 풀면 안된다는 것이죠.

 

여기서 관점을 살짝 비틀어보면 (인접한 두 면을 선택한다) = (서로 평행하는 면을 선택하면 안된다), (한 꼭짓점을 공유하는 세 면을 선택한다) = (세 면에서 두 면이 서로 평행하면 안된다) 라고 생각할 수 있습니다.

 

그래서 면들이 서로 평행하지 않도록 선택하면 됩니다.

코드는 어떤 게 가독성이 좋을지 몰라서 2개 올립니다.

 

 

코드1

n = int(input())
arr = [*map(int, input().split())]
x = min(arr[0], arr[5])
y = min(arr[1], arr[4])
z = min(arr[2], arr[3])
 
if n == 1: print(sum(sorted(arr)[:5]))
else:print(4 * (x + y + z) + 
           (8 * n - 12) * min(x + y, y + z, z + x) + 
           (5 * n * n - 16 * n + 12) * min(arr))

 

코드2

def check(x, y):
    if x == y: return False
    a, b = min(x, y), max(x, y)
    for i in range(3):
        if 2 - i == a and 3 + i == b:
            return False
    return True
 
 
n = int(input())
arr = [*map(int, input().split())]
dice1 = min(sorted(arr))
dice2 = min(arr[i] + arr[j] for i in range(6) for j in range(6) if check(i, j))
dice3 = min(arr[i] + arr[j] + arr[k] for i in range(6) for j in range(6) for k in range(6) if check(i, j) and check(j, k) and check(i, k))
 
if n == 1: print(sum(sorted(arr)[:5]))
else:print(4 * dice3 + (8 * n - 12) * dice2 + (5 * n * n - 16 * n + 12) * dice1)