백준 / 1041 주사위 python3

www.acmicpc.net/problem/1041

1041번: 주사위

그냥 파이썬으로 간단한 문제가 풀고 싶어 푼 문제입니다. 정답률은 낮지만 어렵지는 않은 문제입니다. 

 

같은 주사위 n^3 개를 쌓아 큰 주사위의 5면의 합을 최소로 만드는 문제입니다.

n이 1,000,000 이하이므로, 모든 경우를 다 돌면 시간초과입니다. 

그리고 모두 같은 주사위라는 좋은 조건이 있기 때문에 그냥 최소가 되는 애들로 다 더해주면 됩니다.

 

최소가 되기 위해서는 다음의 경우를 따져봅니다.

1. 한 면만 보이는 경우

한 면만 보이는 주사위는 주사위의 눈 6개 중 최소를 가지면 됩니다.

그리고 큰 주사위의 바닥이 붙어 있으므로 한 면만 보이는 주사위는 ((n-2)^2)*5 + (n-2)*4 가지 입니다.

 

2. 두 면이 보이는 경우

두 면이 보이는 경우는, 모서리 부분 중 꼭짓점 부분이 아닌 부분입니다. 이 경우는 총 (n-2)*4 + (n-1)*4 개 존재합니다.

한 가지 주의할 점은 원래 주사위 6개의 눈으로 조합한 15가지 경우 중 모두가 이 두 면이 보이는 부분을 만들 수는 없습니다. 마주보는 면은 될 수가 없습니다.

 

3. 세 면이 보이는 경우

세 면이 보이는 경우는, 꼭짓점 부분입니다. 이 경우는 4개 입니다. 그리고 주사위 6개의 눈을 3가지로 조합한 경우 (20가지) 모두가 여기에 해당 될 수 없습니다. 코드에 적혀있는 부분만이 해당됩니다.

 

1,2,3 번의 경우에 해당하는 최솟값을 골라 각 경우의 수만큼 곱해 더해주면 됩니다.

(주사위가 1개인 경우는 n-2가 음수이므로 그냥 따로 처리했습니다.)

 

코드는 다음과 같습니다.

n = int(input())
dice = list(map(int,input().split()))

Min = min(dice)

if n==1:
    result = sum(dice)
    result -= max(dice)
    print(result)

else:
    result = 0
    
    # 가운데 부분들
    result += ((n-2)**2)*Min*5
    
    # 밑 면이랑 붙어서 1면만 보이는 주사위
    result += (n-2)*Min*4
    
    # 2면 보이는 주사위
    # 가능한 거 : 2쌍씩 묶는 것 중 (15가지) 마주보는 3가지 빼고
    # 3가지 : (A,F),(B,E),(C,D)
    twoSlide = []
    impossible = [(0,5),(5,0),(1,4),(4,1),(2,3),(3,2)]
    for i in range(6):
        for j in range(6):
            if (i!=j) and ( (i,j) not in impossible):
                twoSlide.append(dice[i]+dice[j])
    
    Min2 = min(twoSlide)
    result += ((n-2)*4 + (n-1)*4)*Min2
    
    # 3면이 보이는 주사위
    # 가능한 거 : (A,D,E),(A,C,E),(A,B,D),(A,B,C),(F,D,E),(F,C,E),(F,B,D),(F,B,C)
    threeSlide = []
    possible = [(0,3,4),(0,2,4),(0,1,3),(0,1,2),(5,3,4),(5,2,4),(5,1,3),(5,1,2)]
    for three in possible:
        (x,y,z) = three
        threeSlide.append(dice[x]+dice[y]+dice[z])
    
    Min3 = min(threeSlide)
    result += 4*Min3
    
    print(result)