[BOJ][🟡5][백준#01041] 주사위

문제 출처

BAEKJOON Online Judge #1041

문제

+---+        
| 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보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제

예제 1

입력

2
1 2 3 4 5 6

출력

36

예제 2

입력

3
1 2 3 4 5 6

출력

69

예제 3

입력

1000000
50 50 50 50 50 50

출력

250000000000000

예제 4

입력

10
1 1 1 1 50 1

출력

500

My Sol

import sys
from itertools import combinations

def main():
    def calc_min_single():
        return min(arr)

    def calc_min_double():
        S = {comb for comb in combinations(range(6), 2)}
        del_S = {(0, 5), (1, 4), (2, 3)}
        minn = 1000
        for a, b in S - del_S:
            minn = min(minn, arr[a]+arr[b])
        return minn

    def calc_min_triple():
        S = {(0,1,2),(0,1,3),(0,4,2),(0,4,3), (5,1,2),(5,1,3),(5,4,2),(5,4,3)}
        minn = 1000
        for a, b, c in S:
            minn = min(minn, arr[a]+arr[b]+arr[c])
        return minn

    def check_outer():
        min_single = calc_min_single()
        min_double = calc_min_double()
        min_triple = calc_min_triple()

        sq_triple = 4
        sq_double = 4*(N-2)+4*(N-1)
        sq_single = 4*(N-1)*(N-2)+(N-2)**2

        single = min_single * sq_single
        double = min_double * sq_double
        triple = min_triple * sq_triple
        return single + double + triple


    N = int(input())
    arr = list(map(int, input().split()))
    if N==1: return sum(arr)-max(arr)
    return check_outer()

print(main())

밑면을 제외하고 옆면과 윗면으로 구분하여 문제를 해결하려 했다. 가장 위의 4개의 꼭짓점만 3개의 면을 가지고, 4개의 세로 변은 2개의 면, 그리고 나머지는 한 개의 면을 가진다는 점에서 풀이를 착안했다.

1. 입력으로 N과 6개의 수 arr을 받아 처리한다.
2. calc_min_single 함수에서 1개 면을 보이는 경우의 최솟값을 계산한다. 이는 단순히 arr의 최솟값을 취하면 되겠다.
3. calc_min_double 함수에서 2개 면을 보이는 경우의 최솟값을 계산한다. 하나하나 하드코딩하면 총 4+4+4개의 경우의 수가 나오지만 하나하나 쓰기가 싫어서 itertools의 combinations 함수를 사용하여 6C2를 구하고, 서로 마주보는 3가지 경우를 빼주었다. 12가지 경우에서 가장 작은 합을 반환한다.
4. calc_min_triple 함수에서 3개 면을 보이는 경우의 최솟값을 계산한다. 이는 어쩔 수 없이 하드코딩해주었고, 8개의 경우의수이면 되므로 크게 문제가 되지 않았다. 위처럼 합의 최솟값을 구해 반환하였다.
5. check_outer 함수에서 5개 면에서 구해져야 하는 1개면, 2개면, 3개면의 개수를 구해 곱해주었다. 이 각각을 single, double, triple로 지정하였고, 이를 더한 값을 반환하였다.
6. N이 1인 특이 케이스에서만 전체 합에서 최댓값을 빼준 값을 반환하고, 나머지는 check_outer 함수의 반환값으로 계산할 수 있어서 분기처리해 반환하고, main 함수의 반환값을 최종적으로 출력해준다.

결과

맞았습니다!!

모범답안

출처

n=int(input())
a,b,c,d,e,f=map(int,input().split())
if n==1:
	print(a+b+c+d+e+f-max(a,b,c,d,e,f))
else:
	print(min(a,b,c,d,e,f)*(5*n*n-16*n+12)+min(a+c,a+b,a+d,a+e,b+c,b+f,b+d,c+e,c+f,d+e,d+f,e+f)*(8*n-12)+min(a+b+c,a+b+d,a+d+e,a+e+c,b+d+f,b+c+f,c+e+f,d+e+f)*4)

사실 모범답안은 아니고 코드길이와 연산시간이 짧은 풀이를 가져와보았다. 사실 경우의 수를 모두 하드코딩으로 작성하여 minimum을 찾으면 되는 문제긴 했다. 문제를 풀면서도 이게 알고리즘을 요구하나..? 하는 생각을 좀 하긴 했다. 아무튼 그건 그거고 하드코딩인 점을 제외하면 나름 직관적이고 쉽게 풀어낸 풀이였다.