백준 2116 - 주사위 쌓기

문제 설명

천수는 여러 종류의 주사위를 가지고 쌓기 놀이를 하고 있다. 주사위의 모양은 모두 크기가 같은 정육면체이며 각 면에는 1부터 6까지의 숫자가 하나씩 적혀있다. 그러나 보통 주사위처럼 마주 보는 면에 적혀진 숫자의 합이 반드시 7이 되는 것은 아니다.

주사위 쌓기 놀이는 아래에서부터 1번 주사위, 2번 주사위, 3번 주사위, … 의 순서로 쌓는 것이다. 쌓을 때 다음과 같은 규칙을 지켜야 한다: 서로 붙어 있는 두 개의 주사위에서 아래에 있는 주사위의 윗면에 적혀있는 숫자는 위에 있는 주사위의 아랫면에 적혀있는 숫자와 같아야 한다. 다시 말해서, 1번 주사위 윗면의 숫자는 2번 주사위 아랫면의 숫자와 같고, 2번 주사위 윗면의 숫자는 3번 주사위 아랫면의 숫자와 같아야 한다. 단, 1번 주사위는 마음대로 놓을 수 있다.

이렇게 쌓아 놓으면 긴 사각 기둥이 된다. 이 사각 기둥에는 4개의 긴 옆면이 있다. 이 4개의 옆면 중에서 어느 한 면의 숫자의 합이 최대가 되도록 주사위를 쌓고자 한다. 이렇게 하기 위하여 각 주사위를 위 아래를 고정한 채 옆으로 90도, 180도, 또는 270도 돌릴 수 있다. 한 옆면의 숫자의 합의 최댓값을 구하는 프로그램을 작성하시오.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N개의 주사위가 주어졌을 때, 이를 1번부터 차례대로 쌓아 최대 점수를 구하는 것이다.

점수를 구하는 규칙은 아랫면과 윗면을 제외한 4면 중 최대 점수를 택해 모두 더하면 된다.

 

얼핏 보면 어려워 보이지만 간단한 규칙이 숨어있다.

주사위는 마주보는 면이 존재한다.

즉, 어떤 면을 아래로 위치시키면 자동으로 윗면이 정해진다는 뜻이다.

전개도를 보면, A는 F와 B는 D와 C는 E와 마주한다.

이를 편하게 관리하기 위해, 배열을 통해 자신이 마주 보는 면을 미리 계산해 놓을 수 있다.

vector<int> faced = { 0, 6, 4, 5, 2, 3, 1 };

제일 앞에 0은 idx계산시 편의를 위해 추가한 것이다.

1은 A를 의미하며, 2는 B, 6은 F를 의미한다.

 

이제 주사위를 쌓기만 하면 된다.

주사위를 쌓는 과정에서 내가 결정할 수 있는 것은 제일 아래 있는 주사위 하나뿐이다.

즉, 1번 주사위의 어떤 면을 아래로 위치시키는지에 따라 모든 과정이 자동으로 결정된다.

예를 들어 보자.

5
2 3 1 6 5 4
3 1 2 4 6 5
5 6 4 1 3 2
1 3 6 2 4 5
4 1 6 5 2 3

이러한 예시가 주어졌다고 가정해 보자.

1번 주사위를 놓을 때, A면인 2를 아래로 향하게 놓는다고 하면 마주 보는 면 F가 위로 올라간다.

즉, 4가 제일 위로간 형태가 될 것이다.

그럼, 2와 4를 제외한 {1, 3, 5, 6}이 옆면에 있을 것이고 이는 가장 큰 면이 앞으로 오도록 얼마든지 돌릴 수 있기 때문에 최댓값을 고르면 되는 것이다.

이어서, 4가 제일 윗면에 있기 때문에 다음 주사위인 2번 주사위를 놓으려면 4가 아래로 향하도록 놓아야 한다.

그렇다면 D면인 4가 아래로 향하기 때문에 마주 보는 B면이 위로 올라간다.

D면은 4, B면은 1이기 때문에 이를 제외한 {2, 3, 5, 6} 중 최댓값을 고르면 된다.

이러한 방식으로 모든 주사위를 놓으면 한 면을 아래로 놓은 상황의 점수를 구할 수 있다.

이를 1번 주사위의 6면을 아래로 모두 놓아보며 반복하면 된다.

 

계산 과정 중, 편의를 위한 함수가 있다.

우선, 숫자를 알았을 때 어떤 면인지 알아내는 함수가 필요하다.

마주하는 면을 구해야 하기 때문이다.

int GetIdx(vector<int>& dice, int num)
{
    for (int i = 1; i <= 6; i++)
    {
        if (num == dice[i]) return i;
    }

    return -1;
}

 

그리고 두 면을 제외한 수 중 최댓값을 구하는 함수도 필요하다.

int GetMaxNum(int bottom, int top)
{
    vector<bool> temp(7, true);

    temp[bottom] = false;
    temp[top] = false;

    for (int i = 6; i > 0; i--)
    {
        if (temp[i]) return i;
    }

    return -1;
}

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int N;
vector<vector<int>> dices;
vector<int> faced = { 0, 6, 4, 5, 2, 3, 1 };

int GetMaxNum(int bottom, int top)
{
    vector<bool> temp(7, true);

    temp[bottom] = false;
    temp[top] = false;

    for (int i = 6; i > 0; i--)
    {
        if (temp[i]) return i;
    }

    return -1;
}

int GetIdx(vector<int>& dice, int num)
{
    for (int i = 1; i <= 6; i++)
    {
        if (num == dice[i]) return i;
    }

    return -1;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.precision(4);
    
    cin >> N;

    dices.resize(N+1, vector<int>(7));
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= 6; j++)
        {
            cin >> dices[i][j];
        }
    }

    int ans = 0;
    //아래가 정해지면 쭉쭉 정해짐
    for (int i = 1; i <= 6; i++)
    {
        int current = 0;
        //i번 면이 아래로
        int top = dices[1][faced[i]];
        int bottom = dices[1][i];
        current += GetMaxNum(bottom, top);

        for (int j = 2; j <= N; j++)
        {
            int bottomIdx = GetIdx(dices[j], top);
            
            top = dices[j][faced[bottomIdx]];
            bottom = dices[j][bottomIdx];
            
            current += GetMaxNum(bottom, top);
        }

        ans = max(ans, current);
    }

    cout << ans;

    return 0;
}

---