[삼성] 17825 주사위 윷놀이

시뮬레이션 문제로, 나한테는 삼성 기출 중에 상당히 까다로운 문제인 것 같다

 

시간복잡도 계산 시, 브루트 포스로 말의 순서를 정하면 2^20 * 10번의 주사위 * 최대 5번 = 약 5천만으로 1억 안에 해결할 수 있다. map으로 다음 위치로 하나씩 움직이는 점과 모든 말의 순서를 탐색한다는 점이 시간을 오래 걸리게 했다.

 

 

계속 틀렸던 이유는 dfs가 아닌 브루트포스로 접근했는데, 말이 움직이지도 못한 채 다음 턴으로 넘어가도 이 부분에서 쌓여진 합이 답의 일부분이 되었다. 그리고 브루트포스로 하니 확실히 0.3초가 걸리는, 효율적이지 못한 시간복잡도를 보였다

 

문제: https://www.acmicpc.net/problem/17825

깃허브주소: https://github.com/surinoel/boj/blob/master/17825.cpp

깃허브주소(DFS): https://github.com/surinoel/boj/blob/master/17825_dfs.cpp

 

	#include <map>
	#include <vector>
	#include <iostream>
	#include <algorithm>
	using namespace std;
	map<int, int> red = {
	{ 0, 2 },{ 2, 4 },{ 4, 6 },
	{ 6, 8 },{ 8, 10 },{ 10, 12 },
	{ 12, 14 },{ 14, 16 },{ 16, 18 },
	{ 18, 20 },{ 20, 22 },{ 22, 24 },
	{ 24, 26 },{ 26, 28 },{ 28, 30 },
	{ 30, 32 },{ 32, 34 },{ 34, 36 },
	{ 36, 38 },{ 38, 40 },{ 40, 50 }
	};
	map<int, int> blue = {
	{ 10, 13 },{ 13, 16 },{ 16, 19 },
	{ 19, 25 },{ 20, 22 },{ 22, 24 },
	{ 24, 25 },{ 30, 28 },{ 28, 27 },
	{ 27, 26 },{ 26, 25 },
	};
	map<int, int> blue_goal = {
	{ 25, 30 },{ 30, 35 },{ 35, 40 },{ 40, 50 }
	};
	int ans;
	vector<int> die;
	void move(vector<int> &arr) {
	pair<int, int> locate[4] = {
	{ 0, 0 },
	{ 0, 0 },
	{ 0, 0 },
	{ 0, 0 }
	};
	bool tok = true;
	int sum = 0;
	for (int i = 0; i < 10; i++) {
	int mal = arr[i];
	int present = locate[mal].first;
	int dir = locate[mal].second;
	int cnt = die[i];
	if (present == 50) continue;
	for (int j = 0; j < cnt; j++) {
	if (dir == 0) present = red[present];
	else if (dir == 1) present = blue[present];
	else if (dir == 2) present = blue_goal[present];
	if (present == 25) dir = 2;
	else if (present == 50) break;
	}
	if (present == 50) {
	locate[mal].first = present;
	}
	else {
	if (dir == 0 && (present == 10 || present == 20 || present == 30)) {
	dir = 1;
	}
	bool ok = true;
	for (int j = 0; j < 4; j++) {
	if (mal != j) {
	if (present == locate[j].first &&
	( present == 40 || dir == locate[j].second)) {
	ok = false;
	}
	}
	}
	if (ok) {
	locate[mal].first = present;
	locate[mal].second = dir;
	sum += present;
	}
	else {
	tok = false;
	}
	}
	}
	if (tok) {
	ans = max(ans, sum);
	}
	}
	void go(int idx, vector<int> &arr) {
	if (idx == 10) {
	move(arr);
	return;
	}
	for (int i = 0; i < 4; i++) {
	arr[idx] = i;
	go(idx + 1, arr);
	}
	}
	int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	for (int i = 0; i < 10; i++) {
	int x;
	cin >> x;
	die.push_back(x);
	}
	vector<int> arr(10);
	go(0, arr);
	cout << ans << '\n';
	return 0;
	}

view raw 17825.cpp hosted with ❤ by GitHub

 

DFS 코드

 

	#include <map>
	#include <vector>
	#include <iostream>
	#include <algorithm>
	using namespace std;
	map<int, int> red = {
	{ 0, 2 },{ 2, 4 },{ 4, 6 },
	{ 6, 8 },{ 8, 10 },{ 10, 12 },
	{ 12, 14 },{ 14, 16 },{ 16, 18 },
	{ 18, 20 },{ 20, 22 },{ 22, 24 },
	{ 24, 26 },{ 26, 28 },{ 28, 30 },
	{ 30, 32 },{ 32, 34 },{ 34, 36 },
	{ 36, 38 },{ 38, 40 },{ 40, 50 }
	};
	map<int, int> blue = {
	{ 10, 13 },{ 13, 16 },{ 16, 19 },
	{ 19, 25 },{ 20, 22 },{ 22, 24 },
	{ 24, 25 },{ 30, 28 },{ 28, 27 },
	{ 27, 26 },{ 26, 25 },
	};
	map<int, int> blue_goal = {
	{ 25, 30 },{ 30, 35 },{ 35, 40 },{ 40, 50 }
	};
	int ans;
	vector<int> die;
	int move(int idx, int mal, vector<pair<int, int>> &locate) {
	int present = locate[mal].first;
	int dir = locate[mal].second;
	int cnt = die[idx];
	if (present == 50) return 0;
	for (int j = 0; j < cnt; j++) {
	if (dir == 0) present = red[present];
	else if (dir == 1) present = blue[present];
	else if (dir == 2) present = blue_goal[present];
	if (present == 25) dir = 2;
	else if (present == 50) break;
	}
	if (present == 50) {
	locate[mal].first = present;
	}
	else {
	if (dir == 0 && (present == 10 || present == 20 || present == 30)) {
	dir = 1;
	}
	bool ok = true;
	for (int j = 0; j < 4; j++) {
	if (mal != j) {
	if (present == locate[j].first &&
	( present == 40 || dir == locate[j].second)) {
	ok = false;
	}
	}
	}
	if (ok) {
	locate[mal].first = present;
	locate[mal].second = dir;
	return present;
	}
	else {
	return -1;
	}
	}
	return 0;
	}
	void go(int idx, int sum, vector<pair<int,int>> &locate) {
	if (idx == 10) {
	ans = max(ans, sum);
	return;
	}
	for (int i = 0; i < 4; i++) {
	int prev_locate = locate[i].first;
	int prev_dir = locate[i].second;
	int ret = move(idx, i, locate);
	if (ret > -1) {
	go(idx + 1, sum + ret, locate);
	}
	locate[i].first = prev_locate;
	locate[i].second = prev_dir;
	}
	}
	int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	for (int i = 0; i < 10; i++) {
	int x;
	cin >> x;
	die.push_back(x);
	}
	vector<pair<int, int>> locate = {
	{ 0, 0 },
	{ 0, 0 },
	{ 0, 0 },
	{ 0, 0 }
	};
	go(0, 0, locate);
	cout << ans << '\n';
	return 0;
	}

view raw 17825_dfs.cpp hosted with ❤ by GitHub