[BOJ] 2116 - 주사위 쌓기 | C++

문제

 

분석

 

정해진 조건대로 주사위를 쌓아 주사위 탑의 한쪽 면의 합이 최대가 되는 값을 구하는 문제입니다. 주사위 탑을 쌓을 때 아래 주사위의 윗면 숫자와, 위 주사위의 아랫면 숫자가 같아야 한다는 제약 조건이 있습니다.

얼핏 보면 DP스러워 보이기도 합니다만, 완전 탐색으로 해결할 수 있습니다.

 

 

단순화를 위해 주어진 모든 주사위가 그림과 같은 모양이라고 가정하겠습니다.

맨 아래 주사위의 윗면 숫자를 1이라고 정하면 그 위 주사위의 아랫면 숫자는 자동으로 1로 정해집니다. 1의 맞은편 숫자가 6이므로 그 주사위의 윗면 숫자는 6으로 정해지게 되고, 그 다음 주사위의 숫자 역시 자연스럽게 정해지게 됩니다.

즉 맨 아래 주사위의 윗면 숫자만 정하면 나머지 모든 주사위의 위, 아랫면 숫자가 자동으로 정해집니다.

 

그러므로 문제는 위, 아랫면으로 사용하지 않은 네 면 중 최댓값 하나를 구해 모두 더하는 것으로 단순화됩니다.

 

풀이 과정

int n;
vector<array<int, 6>> dices;
constexpr int side[6] = { 5, 3, 4, 1, 2, 0 };

 

dices 변수는 주사위의 정보를 저장합니다.

 

 

side 변수는 마주 보는 면의 인덱스입니다. 위 그림처럼 0번 면에 마주보는 면은 5가 될 것이고, 1번 면에 마주보는 면은 3이 될 것입니다.

문제를 풀 때 인덱스가 같은 면끼리 마주보게 해야 하는 것이 아니라 실제 주사위에 적힌 숫자가 같은 면끼리 마주보게 해야 한다는 점에 주의해야 합니다.

 

int main()
{
	fastip; sws;

	cin >> n;
	dices.resize(n);
	for (auto& dice : dices) {
		for (auto i : views::iota(0, 6)) 
			cin >> dice[i];
	}
	int ans = 0;
	for (auto i : views::iota(0, 6)) {
		ans = max(ans, search(0, dices[0][i]));
	}
	cout << ans;
}

 

main 함수에서는 맨 아래 주사위의 아랫면 숫자를 바꿔 가며 최댓값이 얼마인지 확인합니다. 맨 아래 주사위의 아랫면 숫자가 정해지면 모든 주사위의 아랫면/윗면 숫자가 정해지므로 딱 여섯 번만 완전 탐색 하면 됩니다.

search 함수를 통해 최댓값을 구해 줄 것입니다.

 

int search(int depth, int top)
{
	if (depth == n) return 0;
	int nt, nd;
	for (auto i : views::iota(0, 6)) {
		if (dices[depth][i] == top) {
			nd = i;
			nt = side[i];
			break;
		}
	}
	...
}

 

search 함수는 재귀함수로 구현하였습니다. 함수의 인자로 넘어오는 depth 변수는 몇 번째 주사위를 확인 중인지를 나타내며, top 변수는 이전 주사위의 맨 위 숫자를 나타냅니다. 재귀함수의 종료 조건은 n - 1번 주사위까지 전부 확인했을 때입니다.

 

이번 단계의 주사위 모양을 순회하며 윗면 인덱스(nt)와 아랫면 인덱스(nd)를 저장해 주었습니다.

 

int search(int depth, int top)
{
	...
	int ans = 0;
	for (auto i : views::iota(0, 6)) {
		if (i == nd || i == nt) continue;
		ans = max(dices[depth][i], ans);
	}
	return search(depth + 1, dices[depth][nt]) + ans;
}

 

그리고 다시 한 번 주사위를 순회해 주며 아랫면과 윗면이 아닌 면 중 최댓값을 구해 주었습니다. 이 최댓값이 곧 가장 큰 옆면의 숫자가 되며, 이 값을 더하여 다시 재귀해주면 됩니다.

이번 주사위의 윗면 숫자는 nt가 아니라 dices[depth][nt]임에 유의해야 합니다. nt는 윗면 숫자의 인덱스일 뿐이고, 그 인덱스를 통해 주사위에 적힌 실제 숫자를 전달해야 합니다.

 

소스 코드

#include <iostream>
#include <array>
#include <vector>
#include <ranges>
#define fastip std::cin.tie(nullptr)
#define sws std::ios::sync_with_stdio(false)
#define endl "\n"
using namespace std;

int n;
vector<array<int, 6>> dices;
int side[6] = { 5, 3, 4, 1, 2, 0 };

int search(int depth, int top)
{
	if (depth == n) return 0;
	int nt, nd;
	for (auto i : views::iota(0, 6)) {
		if (dices[depth][i] == top) {
			nd = i;
			nt = side[i];
			break;
		}
	}
	int ans = 0;
	for (auto i : views::iota(0, 6)) {
		if (i == nd || i == nt) continue;
		ans = max(dices[depth][i], ans);
	}
	return search(depth + 1, dices[depth][nt]) + ans;
}

int main()
{
	fastip; sws;

	cin >> n;
	dices.resize(n);
	for (auto& dice : dices) {
		for (auto i : views::iota(0, 6))
			cin >> dice[i];
	}
	int ans = 0;
	for (auto i : views::iota(0, 6)) {
		ans = max(ans, search(0, dices[0][i]));
	}
	cout << ans;
}

 

GitHub - SH4MDEL/boj-algorithm: Solving Baekjoon Online Judge (https://www.acmicpc.net/)

 

위 리포지토리에서 전체 소스코드를 확인하실 수 있습니다.

감사합니다.