백준 1041 주사위 파이썬(Python)

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

1041번: 주사위

문제

주사위는 위와 같이 생겼다. 주사위의 여섯 면에는 수가 쓰여 있다. 위의 전개도를 수가 밖으로 나오게 접는다.

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

 

출력

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

 

---

풀이 방법

N^3개의 주사위를 쌓아서 정육면체를 만들면 주사위의 면이 1개 보이거나 2개 보이거나 3개 보여지는 경우로 나뉜다. 아래의 그림을 보면 N = 4 인 경우 다음과 같다. (a <= b <= c)

그림을 참고하여 정육면체 면에서 1, 2, 3개의 면이 보여지는 주사위 개수를 각각 세어주면 다음과 같이 일반화할 수 있다.

 

1. 면이 1개 보이는 주사위 개수: 4개의 옆면에 각 (N-2) * (N-1) 개, 윗면에 (N-2)**2 개 

2. 면이 2개 보이는 주사위 개수: 4개의 옆면 모서리에 각 (N-1) 개, 4개의 윗면 모서리에 각 (N-2)

3. 면이 3개 보이는 주사위 개수: 윗면 모퉁이에 4개

 

이제 (k개 면이 보여지는 주사위 총 개수) x (k개 면의 최소합) 만 구하여 모두 더해주면 답이 된다.

최소합을 구해주어야 하는데 일단 주사위의 각 면은 서로 마주보는 면,즉 A-F, B-E, C-D 를 제외하고 모든 면이 접해있다. 따라서, 서로 마주보는 면의 두 숫자 중 작은 수를 선택하고, 그렇게 선택된 3개의 숫자를 사용하여

k개의 면이 보이는 주사위의 경우 가장 작은 k개를 합해주면 최소합을 구할 수 있다.

간단한 문제인 것 같지만 쉽지 않았다..

 

코드  

N = int(input())
numbers = list(map(int, input().split()))

if N == 1: # 주사위 한개인 경우
    print(sum(numbers) - max(numbers)) # 주사위의 가장 작은 5개의 숫자 합
else:
    answer = 0
    min_arr = []
    # 서로 마주보는 숫자 두개 중 작은값을 추가
    min_arr.append(min(numbers[0], numbers[5]))
    min_arr.append(min(numbers[1], numbers[4]))
    min_arr.append(min(numbers[2], numbers[3]))
    min_arr.sort() # 오름차순 정렬 

    # 면이 1개 보이는 주사위, 2개 보이는 주사위, 3개 보이는 각 주사위의 면 최소합
    sum1 = min_arr[0]
    sum2 = min_arr[0] + min_arr[1]
    sum3 = sum(min_arr)
    # (K개 면이 보이는 주사위 총 개수) x (k개 면의 합 최소값)
    answer += (4*(N-1)*(N-2) + (N-2)**2) * sum1 
    answer += (4*(N-1) + 4*(N-2)) * sum2
    answer += 4 * sum3
    print(answer)