[99클럽/코딩테스트 챌린지/C++] 주사위 쌓기 문제 해결

문제 링크 :

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

 

문제 요약

이 문제는 여러 개의 주사위를 쌓아 옆면 숫자의 합이 최대가 되도록 하는 문제입니다. 주사위를 쌓을 때 다음 규칙을 지켜야 합니다:

1. 각 주사위의 아래면 숫자는 바로 아래 주사위의 윗면 숫자와 같아야 합니다.
2. 주사위는 회전할 수 있지만, 위아래 위치는 고정됩니다.
3. 옆면의 숫자 중 가장 큰 값을 선택하여 합을 계산합니다.

문제는 옆면 숫자의 합의 최대값을 구하는 것입니다.

문제 해결 접근법

1. 주사위의 위/아래 면 설정

• 주사위의 각 면은 A,B,C,D,E,FA, B, C, D, E, FA,B,C,D,E,F로 표현됩니다.
• 아래 면과 윗면의 관계는 다음과 같습니다:
  • A(0)↔F(5)
  • B(1)↔D(3)
  • C(2)↔E(4)
• 아래 면의 값을 기준으로 위 면의 값을 가져오는 함수 GetUpsideDownValue를 구현했습니다.

2. 첫 번째 주사위의 윗면 설정

• 첫 번째 주사위의 윗면은 모든 경우(6가지)를 고려해야 합니다.
• 이를 통해 모든 가능한 경우를 탐색하며 최대 합을 계산합니다.

3. 옆면 숫자의 최대값 계산

• 각 주사위에서 윗면과 아래면을 제외한 나머지 숫자 중 가장 큰 값을 선택하여 합산합니다.

4. 다음 주사위의 아래면 설정

• 현재 주사위의 윗면 값은 다음 주사위의 아래면 값이 됩니다.
• 이를 반복하며 모든 주사위를 쌓아 옆면의 최대 합을 계산합니다.

코드 설명

#include <iostream>
#include <vector>

using namespace std;

int N; // 주사위 개수
vector<vector<int>> dices; // 주사위 데이터
int answer = 0;

// 주사위의 아래면에 따른 윗면 값 반환
int GetUpsideDownValue(int index, int downIndex) {
    switch (downIndex) {
        case 0: return dices[index][5];
        case 1: return dices[index][3];
        case 2: return dices[index][4];
        case 3: return dices[index][1];
        case 4: return dices[index][2];
        case 5: return dices[index][0];
    }
    return -1;
}

// 특정 윗면 값으로 주사위를 쌓았을 때 옆면 합 계산
int find(int index) {
    int total = 0;
    int upValue = dices[0][index]; // 첫 주사위의 윗면 값
    int maxValue = 0;

    // 첫 주사위의 옆면 최대값 계산
    for (int i = 0; i < 6; i++) {
        if (dices[0][i] == upValue || dices[0][i] == GetUpsideDownValue(0, index)) continue;
        maxValue = max(maxValue, dices[0][i]);
    }
    total += maxValue;

    // 나머지 주사위 처리
    for (int i = 1; i < N; i++) {
        int downValue = 0, downIndex = 0;

        // 현재 주사위에서 아래면 값 설정
        for (int j = 0; j < 6; j++) {
            if (dices[i][j] == upValue) {
                downValue = GetUpsideDownValue(i, j);
                downIndex = j;
                break;
            }
        }

        // 현재 주사위의 옆면 최대값 계산
        maxValue = 0;
        for (int j = 0; j < 6; j++) {
            if (dices[i][j] == upValue || dices[i][j] == downValue) continue;
            maxValue = max(maxValue, dices[i][j]);
        }
        total += maxValue;

        // 다음 주사위의 윗면 값 설정
        upValue = GetUpsideDownValue(i, downIndex);
    }

    return total;
}

int main() {
    cin >> N;
    dices = vector<vector<int>>(N);

    // 주사위 데이터 입력
    for (int i = 0; i < N; i++) {
        dices[i] = vector<int>(6);
        for (int j = 0; j < 6; j++) {
            cin >> dices[i][j];
        }
    }

    // 첫 번째 주사위의 모든 윗면 경우 탐색
    for (int i = 0; i < 6; i++) {
        int temp = find(i);
        answer = max(answer, temp);
    }

    cout << answer << endl;
    return 0;
}

 

배운 점

1, 윗면과 아래면 관계 구현 : 주사위의 면과 반대면의 관계를 명확히 정의하고, 이를 코드로 효율적으로 구현하는 방법을 배웠습니다.

2, 완전 탐색의 활용 : 첫 번째 주사위의 모든 윗면 값을 탐색하여 가능한 모든 경우를 확인하는 완전 탐색을 구현했습니다.

3, 최대값 갱신 로직 : 각 주사위에서 옆면의 최대값을 계산하여 총합을 구하고, 이를 통해 최대값을 갱신하는 방법을 익혔습니다.

4, 다차원 배열 활용 : 주사위 데이터를 다차원 배열로 저장하고, 이를 기반으로 필요한 값을 효율적으로 처리하는 방법을 배웠습니다.

결론

이 문제를 통해 주사위의 특성을 활용한 탐색 문제를 해결하는 방법을 학습할 수 있었습니다. 특히, 면 간의 관계를 정의하고, 이를 기반으로 문제를 구조적으로 접근하는 중요성을 깨달았습니다. 앞으로도 유사한 완전 탐색 문제에서 이 접근 방식을 활용할 수 있을 것입니다. 😊