알고리즘 - Python / 백준 - 1041번 : 주사위

1041번: 주사위 (acmicpc.net)

1041번: 주사위

 

---

풀이

• 주사위를 쌓아 보이는 면의 숫자합이 가장 작도록 쌓고 그 합을 구하는 문제이다.
• 주사위를 놓을 때 한 면만 보이는 경우 , 두면이 보이는 경우 , 세면이 보이는 경우로 나뉜다.
• 한 면의 경우는 주사위 6개의 면중 가장 작은 수 , 두면의 경우는 그리디 알고리즘을 통해 가장 숫자가 작은 면과 붙어있는 4개의 면중 그다음으로 작은 면을 고르면 된다.
• 세면의 경우도 그리디 알고리즘으로 구현하려 했으나 생각해보니 선택하는 면의 개수가 늘어날 수록 발생하는 경우가 얼마 되지 않을 것 같아 직접 세어보았다.
• 세면의 경우 총 8개의 조합이 발생할 수 있었다.
• 따라서 , 세면의 경우는 8개의 조합중 최솟값을 택하도록 구현하였다.

 

import sys

def check_2(stack,min_idx):
    check_min = 51
    new_min_idx = -1
    for i in range(0,6):
        if i != min_idx and i != 5-min_idx:
            if check_min > stack[i]:
                check_min = stack[i]
                new_min_idx = i
    return new_min_idx

def check_new_3(stack):
    r = min(
        stack[0] + stack[1] + stack[2],
        stack[0] + stack[1] + stack[3],
        stack[0] + stack[2] + stack[4],
        stack[0] + stack[4] + stack[3],
        stack[1] + stack[2] + stack[5],
        stack[1] + stack[3] + stack[5],
        stack[2] + stack[4] + stack[5],
        stack[3] + stack[4] + stack[5]
        )
    return r

n = int(sys.stdin.readline())
dice = list(map(int, input().split()))
min_dice = min(dice)
min_idx = dice.index(min_dice)
if n > 2:
    ans = (min_dice*((n-2)*((5*n)-6)))
else:
    ans = 0


min_2sidx  = check_2(dice,min_idx)
min_2side = min_dice + dice[min_2sidx]

if n > 2:
    ans += int((min_2side)*((2*n)-3) * 4)
elif n == 2:
    ans += int(min_2side*4)

side_3 = check_new_3(dice)

if n == 1:
    ans_1 = 0
    for i in range(0,6):
        ans_1 += dice[i]
    print(ans_1-max(dice))
elif n > 1:
    ans += 4*(side_3)
    print(ans)

---