[백준][C++] 1041: 주사위

문제 링크: https://www.acmicpc.net/problem/1041

 

흥미로웠던 문제입니다.

일단 생각할 수 있는 건 {A, B, C, D, E, F} 중에서 가장 작은 값을 다 바깥쪽으로 하면 될 것 같다는 느낌이 옵니다. 하지만 꼭지점과 모서리부분을 생각해줘야 합니다.

꼭지점에 배치되는 주사위는 3면이 보이고, 모서리에 배치되는 주사위는 2면이 보입니다. 나머지는 전부 1면이 보이고요.

 

일단 꼭지점, 모서리와 나머지 칸의 개수를 어떻게 셀까요?

 

Fig 1. 꼭지점(다이아몬드, 파란색), 모서리(초록색, 에메랄드), 그리고 나머지(흰색, 철)를 나타낸 모습  

그림을 그리려다가 귀찮아서 마인크래프트로 대충 블록을 쌓아서 만들었습니다.

 

n이 정육면체의 한 변의 길이라고 할 때, 꼭지점, 모서리, 그리고 나머지 칸의 개수는 아래와 같습니다.

• 꼭지점: 무조건 4개입니다
• 모서리: 8n-12
  • 지면과 수직인 선분: 4개 * (n-1)
  • 지면과 수평인 선분: 4개 * (n-2)
• 나머지 면: \(5n^2 -16n+12\)
  • 윗면: (n-2) * (n-2)
  • 옆면: 4개 * (n-2) * (n-1)

복잡해 보이지만 그림을 그려보면 쉽게 알 수 있습니다.

 

나머지 면은 주사위에서 가장 작은 수가 보이게 놓으면 되는데, 꼭지점과 모서리는 어떻게 해야 3면, 2면의 수의 합이 최소가 될까요?

주사위의 수 중에서 작은 수 3개, 2개를 구하면 될까요? 안됩니다. 인접한 면끼리의 숫자여야 하기 때문입니다.

 

구현 방법이 여러가지 있겠지만 저는 간단하게 아래 방법으로 구했습니다.

• 꼭지점: {주사위의 옆면 두개 + 윗면 또는 아랫면} 중 최소값을 찾습니다
• 모서리: {주사위의 옆면 두개}, {옆면 하나 + 윗면 또는 아랫면} 중 최소값을 찾습니다.

이렇게 하려면 먼저 입력값을 좀 손봐야 합니다.

Fig 2.

옆면과 위, 아랫면을 분리해줍니다. 배열을 하나 더 만들든가 해서 적당히 분리해주세요.

그 다음은 위에 써있는대로 그대로 구현하면 됩니다

 

#pragma GCC optimize ("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;


const int INF = 987654321;
typedef long long ll;

int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    ll n;
    cin >> n;
    vector<int> dice(6);
    for (auto& c : dice)
        cin >> c;
    
    /*
    이 모양으로 재배치
        +---+
        | E |
    +---+---+---+---+
    | A | B | C | D |
    +---+---+---+---+
        | F |
        +---+
     */
    vector<int> new_dice(6);
    new_dice[0] = dice[4];
    new_dice[1] = dice[0];
    new_dice[2] = dice[1];
    new_dice[3] = dice[5];
    new_dice[4] = dice[3];
    new_dice[5] = dice[2];


    // 제일 큰 면이 바닥에 가도록
    if (n == 1) {
        cout << accumulate(dice.begin(), dice.end(), 0) - *max_element(dice.begin(), dice.end()) << '\n';
        return 0;
    }

    /*
     (n>=2)

     꼭지점: 4개
     모서리: 8n-12개
     나머지: 5n^2-16n+12
     */

    int min_vertex = INF;
    for (int i = 0; i < 4; ++i) {
        int sum = new_dice[i] + new_dice[(i + 1)%4];
        for (int j = 4; j <= 5; ++j) {
            min_vertex = min(min_vertex, sum + new_dice[j]);
        }
    }

    int min_side = INF;
    for (int i = 0; i < 4; ++i) {
        min_side = min(min_side, new_dice[i] + new_dice[(i + 1) % 4]);
        for (int j = 4; j <= 5; ++j) {
            min_side = min(min_side, new_dice[i] + new_dice[j]);
        }
    }


    ll sum = 0;
    sum += min_vertex * 4;
    sum += min_side * (8 * n - 12);
    sum += *min_element(dice.begin(), dice.end()) * (5 * n * n - 16 * n + 12);
    cout << sum << '\n';

    return 0;
}

구현시 유의할 점은 n==1일 때 예외처리, 그리고 int 오버플로우가 발생할 수 있으니 64비트 정수형을 사용하는것 정도가 있겠습니다.

3면, 2면의 최소값을 구하는 더 깔끔한 방법이 없을까요 궁금하네요