[BOJ] 2116:주사위 쌓기

 

 

0. 문제

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

2116번: 주사위 쌓기

 

1. 문제분석

- 이 문제는 주사위 번호가 증가할 수록, 조건을 만족하는 면들 중 가장 값이 큰 면을 선택하면 된다. 따라서 단순한 그리디 알고리즘 문제이다. 또한 조건을 만족하는 모든 경우의 수를 탐색해야 하므로 완전탐색 알고리즘도 사용하였다.

 

2. 유의할 점

-  마주보는 두 주사위 면을 한 세트로 묶는 것이 좋다. 이를 위해서 나는 n번 주사위의 n번째 면이 갖는 값을 나타내는 2차원 배열(d[10001][6])을 사용했고, 값 입력 시에 abcdef 순서가 아닌 abcfde 순으로 값을 입력했다.(마주보는면 = (현재 면 + 3) % 6)

-  재귀호출을 통해 모든 경우의 수를 탐색하는데, 이 때 축적되는 최대 면의 값을 계산해주기 위해, 재귀 함수가 호출될 때 해당 면의 값을 더해주고(accum += tmp), 호출이 끝나면 다시 그 값을 제외해주어(accum -= tmp) 다른 경우의 수도 탐색할 수 있도록 했다.

 

3. 소스코드(C++)

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#define endl '\n'
#define INF 987654321
using namespace std;
typedef pair<int, int> ii;

int n, ans, accum;
int d[10001][6];

void go(int now_dice, int prev_val) {
	if (now_dice == n) {
		ans = max(ans, accum);
		return;
	}
	for (int now_side = 0; now_side < 6; now_side++) {
		if (d[now_dice][now_side] != prev_val) continue;
		int tmp = -1;
		for (int j = 0; j < 3; j++) {
			if (j == now_side || j + 3 == now_side) continue;
			tmp = max(tmp, d[now_dice][j]);
			tmp = max(tmp, d[now_dice][j + 3]);
		}
		accum += tmp;
		go(now_dice + 1, d[now_dice][(now_side + 3) % 6]);
		accum -= tmp;
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		// a b c d e f -> a b c / f d e
		cin >> d[i][0] >> d[i][1] >> d[i][2]
			>> d[i][4] >> d[i][5] >> d[i][3];
	}
	for (int i = 0; i < 6; i++) go(0, d[0][i]);
	cout << ans;
	return 0;
}

 

 

4. 여담

- solved.ac의 문제 기준 상 골드 3에 해당하는 문제였는데, 문제 난이도에 비해선 꽤 쉬운 문제였다. 그래서인지 정답비율도 60%가 넘을 정도로 높은편...