파이썬 알고리즘 216번 | [백준 1041 번] 주사위 - 그리디

216. 주사위

1) 어떤 전략(알고리즘)으로 해결?

• 그리디 : 가장 최소를 구하자
• 세면, 두면, 한면 이 주사위에서 후보들로 쓰이는데 각 면의 경우당 가장 최솟값 구해서 그 합 출력하면 over

2) 코딩 설명

<내 풀이>

import sys
n = int(sys.stdin.readline().strip())
dice = list(map(int, (sys.stdin.readline().strip()).split()))

# 총 세개, 두개 , 한개 이음면 후보들을 각 구해서 가장 작은애가 대표
oned = min(dice)
#############################
twod_candidates = [
    [0,4], [0,1], [0,3], [0,2],
    [1,2], [1,3], [1,5],
    [2,5], [2,4],
    [3,4], [3,5], # (3,5) 와 (4,5) 경우를 누락했었다;; 
    [4,5]
]
twod = 100000001
for x,y in twod_candidates:
    if twod > dice[x]+dice[y] :
        twod = dice[x]+dice[y]
################################
three_candidates = [
    [0,1,2], [0,2,4],[0,3,4], [0,1,3],
    [5,2,1], [5,2,4], [5,4,3], [5,1,3]
]
threed = 100000001
for x,y,z in three_candidates:
    if threed > dice[x]+dice[y]+dice[z] :
        #print(x,y,z, dice[x]+dice[y]+dice[z])
        threed =  dice[x]+dice[y]+dice[z] 
#################################

if n==1 : 
    maxn = max(dice)
    print(sum(dice)-maxn)
else :  # 2~
    top = threed*4 + twod*((n-2)*4) + oned*((n-2)*(n-2))
    common = twod*4 + oned*((n-2)*4)
    print(top + common*(n-1))

< 내 틀렸던 풀이, 문제점>

10 프로 틀림

import sys
n = int(sys.stdin.readline().strip())
dice = list(map(int, (sys.stdin.readline().strip()).split()))

# 총 세개, 두개 , 한개 이음면 후보들을 각 구해서 가장 작은애가 대표
oned = min(dice)
#############################
twod_candidates = [
    [0,4], [0,1], [0,3], [0,2],
    [1,2], [1,3], [1,5],
    [2,5], [2,4],
    [3,4], [4,5]
]
twod = 100000001
for x,y in twod_candidates:
    if twod > dice[x]+dice[y] :
        twod = dice[x]+dice[y]
################################
three_candidates = [
    [0,1,2], [0,2,4],[0,3,4], [0,1,3],
    [5,2,1], [5,2,4], [5,4,3], [5,1,3]
]
threed = 100000001
for x,y,z in three_candidates:
    if threed > dice[x]+dice[y]+dice[z] :
        threed =  dice[x]+dice[y]+dice[z] 
#################################

if n==1 : # 0,1,2  
    top = threed*4
else :  # 2보다 큰 것들
    top = threed*4 + twod*((n-2)*4) + oned*((n-2)*(n-2))

common = twod*4 + oned*((n-2)*4)
#print(threed, top, twod, oned, common)
print(top + common*(n-1))

아래 반례 수정, 그러나 15% 틀림 ㅎㅎ,,

1 
1 2 3 4 5 6

답 : 15
나의 틀린 출력 : 24

수정 후 코드

import sys
n = int(sys.stdin.readline().strip())
dice = list(map(int, (sys.stdin.readline().strip()).split()))

# 총 세개, 두개 , 한개 이음면 후보들을 각 구해서 가장 작은애가 대표
oned = min(dice)
#############################
twod_candidates = [
    [0,4], [0,1], [0,3], [0,2],
    [1,2], [1,3], [1,5],
    [2,5], [2,4],
    [3,4], [4,5]
]
twod = 100000001
for x,y in twod_candidates:
    if twod > dice[x]+dice[y] :
        twod = dice[x]+dice[y]
################################
three_candidates = [
    [0,1,2], [0,2,4],[0,3,4], [0,1,3],
    [5,2,1], [5,2,4], [5,4,3], [5,1,3]
]
threed = 100000001
for x,y,z in three_candidates:
    if threed > dice[x]+dice[y]+dice[z] :
        threed =  dice[x]+dice[y]+dice[z] 
#################################

if n==1 : # 0,1,2  
    maxn = max(dice)
    print(sum(dice)-maxn)
else :  # 2보다 큰 것들
    top = threed*4 + twod*((n-2)*4) + oned*((n-2)*(n-2))
    common = twod*4 + oned*((n-2)*4)
    #print(threed, top, twod, oned, common)
    print(top + common*(n-1))

<반성 점>

<배운 점>