[개쉬운 풀이] 백준 2116 주사위 쌓기

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

2116번: 주사위 쌓기

문제 

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

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

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

입력

첫줄에는 주사위의 개수가 입력된다. 그다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적힌 숫자가 그림 1에 있는 주사위의 전개도에서 A, B, C, D, E, F의 순서로 입력된다. 입력되는 숫자 사이에는 빈칸이 하나씩 있다. 주사위의 개수는 10,000개 이하이며 종류가 같은 주사위도 있을 수 있다.

출력

첫줄에 한 옆면의 숫자의 합이 가장 큰 값을 출력한다.

 

생각

가장 먼저 든 생각은 주어진 입력값을 내 입맛대로 조절하는 것이다.

입력갑이 A B C D E F 순서로 주어지지만 예시의 그림을 토대로 바라보면 

A - F

B - D

C - E

와 같이 반대면의 쌍을 이룬다. 

따라서 나는 A B C D E F의 입력값을 A B C F D E로 저장하였다. 그러므로 바닥에 깔리는 숫자 under의 인덱스를 i라고 한다면 반대 top의 숫자에 해당하는 인덱스는 (i+3)%6이다.

다음 조건을 바라보니 4개의 옆면 중에서 합이 최대가 되도록 주사위를 쌓고자 하므로 위와 아래에 깔리는 숫자들을 제외하고 최대의 숫자를 구하면 정답이라고 생각하였다.

구현 조건 : 

1. A B C D E F의 입력값을 A B C F D E로 바꾸기

2. under와 쌍을 이루는 인덱스 구현 

3. 각 주사위별 아래와 위에 들어가는 숫자를 판단.

4. 해당 숫자들을 제외한 최대 숫자들의 합 구하기. 

 

코드

void input(){
    cin >> n;
    dices.resize(n, vector<int>(6));
    for(int i = 0; i < n; i++){
        // a b c d e f
        for(int j = 0; j < 3; j++){
            cin >> dices[i][j];
        }
        //하드코딩
        cin >> dices[i][4];
        cin >> dices[i][5];
        cin >> dices[i][3];
       
    }
}

하드 코딩이지만 실제 코테에서 간단한 작업을 진행하는데 이만한 속도가 없다. 

// opposite index
int opIdx(int i){
    return (i+3) % 6;
}

// num번째 주사위에 num-1의 top은 num의 under가 되므로
int nextDiceIdx(int num, int top){
    for(int i = 0; i < 6; i++){
        if(dices[num][i] == top) return opIdx(i);
    }
    return 0;
}

원 배열에서 서로 마주 보는 인덱스를 찾는다고 생각하면 편하다. 우리는 이렇게 쉬운 인덱싱을 하기 위해 입력값을 설계하였다.

 

// under와 top을 제외한 가장 큰 수 (주사위는 1~6 숫자만 갖는다)
int getMax(int under, int top){
    int maxValue;
    for(int i = 6; i >= 1; i--){
        if(i == under || i == top) continue;
        maxValue = i;
        break;
    }
    return maxValue;
}

일반적인 범위 내에서 max값을 찾는 방법이다. 위아래 값들을 배제하고 찾으면 된다.

 

int n;
vector<vector<int>> dices;

//다음 주사위에서 아래와 위 값에 해당하는 인덱스를 찾기 위함
int nextDiceIdx(int num, int top){
    for(int i = 0; i < 6; i++){
        if(dices[num][i] == top) return opIdx(i);
    }
    return 0;
}

void sol(){
    int maximum = 0;
    //나올수 있는 경우에서 최대값을 찾아야 함
    for(int i = 0; i < 6; i++){
        int under = dices[0][i];
        int top = dices[0][opIdx(i)];
        int num = 0;
        int tmp = 0;
        while(true){
            tmp += getMax(under,top);
            num++;
            //초과된 주사위를 계산하지 않도록 함
            if(num == n) break;
            int underidx = nextDiceIdx(num, top);
            top = dices[num][underidx];
            under = dices[num][opIdx(underidx)]; 
        }
        if(maximum < tmp) maximum = tmp;
    }
    cout << maximum << endl;
}

주어진 주사위 개수와 나올 수 있는 모든 경우의 수를 고려하여 최댓값을 구해야 하므로 완전탐색으로 진행하였다.

* 완전탐색이라고 생각이 되면 '어떻게 더 쉽게 풀 수 있을까?' 보다는 그냥 남들도 떠올리는 방법으로 구현을 하고 그 내에서 탐색하는 범위를 줄여 시간초과를 면하는 문제들이 더 많다.

해당 문제에서는 가장 처음 주어지는 주사위를 기준으로 6면을 모두 under에 깔린다는 가정으로 탐색을 진행하였다. (첫 for)

처음 under와 top를 초기화 한 이후 top과 under 값들은 계속 바뀌기 때문에 while문을 통해 바꾸어 주면서 getMax로 해당 주사위에서 가장 큰 값들을 찾고 tmp에 더해주었다. 해당 과정이 모두 끝나면 maximum과 비교하여 최종적으로 우리가 찾는 값들을 찾아주었다.

 

전체 코드

 

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<vector<int>> dices;

int opIdx(int i){
    return (i+3) % 6;
}

void input(){
    cin >> n;
    dices.resize(n, vector<int>(6));
    for(int i = 0; i < n; i++){
        // a b c d e f
        for(int j = 0; j < 3; j++){
            cin >> dices[i][j];
        }
        cin >> dices[i][4];
        cin >> dices[i][5];
        cin >> dices[i][3];
       
    }
}

int getMax(int under, int top){
    int maxValue;
    for(int i = 6; i >= 1; i--){
        if(i == under || i == top) continue;
        maxValue = i;
        break;
    }
    return maxValue;
}

int nextDiceIdx(int num, int top){
    for(int i = 0; i < 6; i++){
        if(dices[num][i] == top) return opIdx(i);
    }
    return 0;
}

void sol(){
    int maximum = 0;
    for(int i = 0; i < 6; i++){
        int under = dices[0][i];
        int top = dices[0][opIdx(i)];
        int num = 0;
        int tmp = 0;
        while(true){
            tmp += getMax(under,top);
            num++;
            if(num == n) break;
            int underidx = nextDiceIdx(num, top);
            top = dices[num][underidx];
            under = dices[num][opIdx(underidx)]; 
        }
        if(maximum < tmp) maximum = tmp;

    }
    cout << maximum << endl;
}

int main(){
    input();
    sol();
    return 0;
}