백준 2116번 주사위 쌓기 - C++

문제

---

천수는 여러 종류의 주사위를 가지고 쌓기 놀이를 하고 있다. 주사위의 모양은 모두 크기가 같은 정육면체이며 각 면에는 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개 이하이며 종류가 같은 주사위도 있을 수 있다.

그림 1

 

출력

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

 

문제 링크

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

 

풀이

---

우선순위 큐와 완전탐색으로 해결할 수 있는 문제다.

 

우선 문제에 나와있는 대로, 주사위는 이렇게 들어온다. (마주보고 있는 주사위의 인덱스는 패턴 배열을 지정해서 쌍을 만들어 구했다.) ▼

 

이 문제에서 나머지 4개의 면은 약간 허상과 같다.

이 중 가장 큰 값만 찾으면 그만이기 때문이다.

 

이렇게 위와 아래만 고정되면 나머지 4면은 자유롭게 돌리기가 가능해지기 때문에 우리는 당연히 가장 큰 값들이 똑같은 방향을 바라보게 설정할 것이다. ▼

 

그렇기에

 

1. 일단 다 쌓아놓고,

2. 가장 큰 수가 나오게 모두 회전시킨 뒤,

3. 값을 모두 더한 다음,

4. 이를 6번 반복하여 가장 큰 값을 찾기!

 

를 하면 된다. ▼

 

 

"회전을 어떻게 시키는데?"

 

 

관건은 회전을 어떻게 하냐? 인데 당연히 실제로 회전을 시킬 생각은 없고, 가장 큰 값을 찾는 로직을 세우면 되는데 필자는 우선순위큐를 주사위 개수만큼 만들어서 할당했다.

 

우선순위큐에 나머지 4개의 값을 넣으면 알아서 가장 큰 값이 `top()`에 배정되니, 다 쌓고 나서는 `top()`만 조회하여 합을 구했다. ▼

 

이걸 6번 반복하고 그 중에서도 가장 큰 값을 반환하면 문제는 해결된다.

 

 

C++ 코드

---

#include <iostream>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

int N, answer;
vector<int> dice[10001];
int pattern[6] = {5, 3, 4, 1, 2, 0};

void input() {
  cin >> N;

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < 6; j++) {
      int A;

      cin >> A;
      dice[i].push_back(A);
    }
  }
}

void solve() {

  for (int i = 0; i < 6; i++) {
    priority_queue<int> q[10001];
    int next = dice[0][pattern[i]];
    int sum = 0;

    for (int j = 0; j < 6; j++) {
      if (j == i || j == pattern[i]) continue;
      q[0].push(dice[0][j]);
    }

    for (int j = 1; j < N; j++) {
      int idx = 0;
      for (int k = 0; k < 6; k++) {
        if (dice[j][k] == next) {
          idx = k;
          break;
        }
      }
      next = dice[j][pattern[idx]];
      for (int k = 0; k < 6; k++) {
        if (k == idx || k == pattern[idx]) continue;
        q[j].push(dice[j][k]);
      }
    }
    for (int j = 0; j < N; j++) {
      sum += q[j].top();
    }
    answer = max(sum, answer);
  }
}

void output() {
  cout << answer;
}


int main() {
  input();
  solve();
  output();
}