백준 1041번 주사위 C++ 풀이

백준 1041번 주사위 C++ 풀이

    +---+        
    | D |        
+---+---+---+---+
| E | A | B | F |
+---+---+---+---+
    | C |        
    +---+       

1. 문제설명
   • 주사위는 위와 같이 생기고, 해당 주사위를 N^3개를 가지고 있어 탁자 위에 NxNxN 크기의 정육면체를 만들려고한다.
     이 때 5개의 면에 쓰여있는 수의 합의 최솟값을 출력하는 프로그램을 작성하시오
2. 입력예시

   2 // = n 
   1 2 3 4 5 6 // = A B C D E F
   

   처음 문제를 보았을 때 정육면체에서 보이는 주사위의 종류를 먼저 정리하였다.

3. 3개의 면이 보이는 주사위는 8개의 꼭짓점 중 윗면 꼭짓점 4개가 유일하다.
4. 2개의 면이 보이는 주사위는 바닥면의 꼭짓점을 포함하여 세로 모서리 4개, 각각 (n-1)개로 4(n-1)개
   윗면의 가로 모서리 4개,각각 (n-2)개로 총 4(n-1) + 4*(n-2)개 이다.
5. 1개의 면이 주사위는 바닥 모서리를 포함하여 4개의 옆면은 (n-1)(n-2), 윗면은 (n-2)(n-2)개로
   총 4(n-1)(n-2) + (n-2)*(n-2)개 이다.

정육면체 총합

(주사위 3개의 면 합 * 4) + 주사위 2개의 면 합 * 4 * (2n-3) + 주사위 1개의 면 합*(4(n-1)(n-2) + (n-2)(n-2))

위의 식으로 표현할 수 있으며 해당 값이 최소 값이 될려면 주사위의 3개의 면, 2개의 면, 1개의 면 각각 최솟값을 찾으면 된다고 생각했다.

1개 면의 최소값을 구하는 것은 단순하였는데 2개,3개에 대한 최소값을 구하는데 있어서 인접하는 2개 또는 3개의 면에 대한 합이라는 조건에 대해서 해결하려는 방법을 찾는데 시간이 걸린 것 같았다.

결국 위의 주사위를 보면 각각 마주 보는 주사위 면이 3 쌍이 존재하는 것을 발견하여 (A,F) , (B,E) , (C,D) 중에 작은 값들을 선택하면 무조건 인접한 면이라는 것을 알 수 있었다.

저 3쌍의 최소 값을 통해서 합을 구해 계산하면 쉽게 구할 수 있고 값의 범위를 고려하지 않아서 예제에 대한 정답이 틀리게 나와 많이 헤맸었다.

#include <iostream>
#include <algorithm>

using namespace std;

int dice[6];
// (0,5) , (1,4)   (2,3)
// (A,F) , (B,E) , (C,D)
int main(){
    int maxVal = 0;
    long long n;
    long long answer = 0;
    cin >> n;
    
    for(int i = 0; i < 6; i++){
        cin >> dice[i];
        answer += dice[i];
        maxVal = max(maxVal,dice[i]);
    }

    if(n == 1){
        answer -= maxVal;
    }else{
        answer = 0;
        int minValue[3];
        minValue[0] = min(dice[0],dice[5]);
        minValue[1] = min(dice[1],dice[4]);
        minValue[2] = min(dice[2],dice[3]);

        sort(minValue, minValue+3);
        
        int sum1 = minValue[0];
        int sum2 = sum1 + minValue[1];
        int sum3 = sum2 + minValue[2];

    //8개 꼭짓점 중 4개는 3면 4개는 2면
    //2개의 면 보이는 세로 4 (n-1)개 , 윗면 가로 4개는 (n-2)개
    //옆면 4개는 (n-1)*(n-2), 윗면 1개는 (n-2)*(n-2);
        answer += sum3 * 4;
        answer += sum2 * 4 * (2*n - 3);
        answer += sum1 * (4*(n-1)*(n-2) + (n-2)*(n-2));

    }

    cout << answer << "\n";


    return 0;
}