백준 17825번 주사위 윷놀이

문제 링크입니다: https://www.acmicpc.net/problem/17825

17825번: 주사위 윷놀이

각 칸마다 도, 개, 걸, 윷, 모 가 나올 때 도착할 수 있는 지점을 미리 저장해놓고 모든 경우의 수를 시뮬레이션을 돌려 풀었던 문제였습니다.

말은 총 4개이고 주사위는 10번 굴렸기 때문에 4^10 즉, 2^20 이기 때문에 시간 내 돌아갈 수 있다는 것은 자명합니다.

각 말은 0, 1, 2, 3 으로 표시하였고 이진수로 00, 01, 10, 11 과 같이 표현했습니다.

따라서, 각 말은 길이가 2인 이진수로 표현할 수 있고 주사위는 총 10번 굴렸기 때문에 MAX를 2 * 10으로 지정하여

for (int pieces = 0; pieces < (1 << MAX); pieces++)

  와 같이 반복문을 돌려 모든 경우의 수를 시뮬레이션 돌렸습니다.

 

	#include <iostream>
	#include <algorithm>
	using namespace std;
	const int MAX = 2 * 10;
	const int SPOT_MAX = 33;
	const int START = 0;
	const int FINISH = 32;
	typedef struct
	{
	int score;
	int nextIdx[5];
	}Spot;
	int result = -1;
	int dices[10];
	Spot spots[SPOT_MAX] = {
	{ 0,{ 1, 2, 3, 4, 5 } },
	{ 2,{ 2, 3, 4, 5, 10 } },
	{ 4,{ 3, 4, 5, 10, 11 } },
	{ 6,{ 4, 5, 10, 11, 12 } },
	{ 8,{ 5, 10, 11, 12, 13 } },
	{ 10,{ 6, 7, 8, 9, 25 } },
	{ 13,{ 7, 8, 9, 25, 26 } },
	{ 16,{ 8, 9, 25, 26, 27 } },
	{ 19,{ 9, 25, 26, 27, FINISH } },
	{ 25,{ 25, 26, 27, FINISH, FINISH } },
	{ 12,{ 11, 12, 13, 14, 17 } },
	{ 14,{ 12, 13, 14, 17, 18 } },
	{ 16,{ 13, 14, 17, 18, 19 } },
	{ 18,{ 14, 17, 18, 19, 20 } },
	{ 20,{ 15, 16, 9, 25, 26 } },
	{ 22,{ 16, 9, 25, 26, 27 } },
	{ 24,{ 9, 25, 26, 27, FINISH } },
	{ 22,{ 18, 19, 20, 21, 28 } },
	{ 24,{ 19, 20, 21, 28, 29 } },
	{ 26,{ 20, 21, 28, 29, 30 } },
	{ 28,{ 21, 28, 29, 30, 31 } },
	{ 30,{ 22, 23, 24, 9, 25 } },
	{ 28,{ 23, 24, 9, 25, 26 } },
	{ 27,{ 24, 9, 25, 26, 27 } },
	{ 26,{ 9, 25, 26, 27, FINISH } },
	{ 30,{ 26, 27, FINISH, FINISH, FINISH } },
	{ 35,{ 27, FINISH, FINISH, FINISH, FINISH } },
	{ 40,{ FINISH, FINISH, FINISH, FINISH, FINISH } },
	{ 32,{ 29, 30, 31, 27, FINISH } },
	{ 34,{ 30, 31, 27, FINISH, FINISH } },
	{ 36,{ 31, 27, FINISH, FINISH, FINISH } },
	{ 38,{ 27, FINISH, FINISH, FINISH, FINISH } },
	{ 0,{ FINISH, FINISH, FINISH, FINISH, FINISH } }
	};
	void func(int pieces)
	{
	int scores[4] = { 0, };
	int idx[4] = { 0, };
	int onSpotCnt[SPOT_MAX] = { 0, };
	// 초기에 0 번째 idx에 4개의 말이 존재
	onSpotCnt[START] = 4;
	for (int i = 0; i < 10; i++)
	{
	int currentPiece = pieces & 3;
	pieces /= 4;
	int nextIdx = spots[idx[currentPiece]].nextIdx[dices[i] - 1];
	if (nextIdx != FINISH && onSpotCnt[nextIdx] > 0)
	{
	return;
	}
	onSpotCnt[idx[currentPiece]]--;
	onSpotCnt[nextIdx]++;
	idx[currentPiece] = nextIdx;
	scores[currentPiece] += spots[nextIdx].score;
	}
	int total = 0;
	for (int piece = 0; piece < 4; piece++)
	{
	total += scores[piece];
	}
	result = max(result, total);
	}
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	for (int i = 0; i < 10; i++)
	{
	cin >> dices[i];
	}
	for (int pieces = 0; pieces < (1 << MAX); pieces++)
	{
	func(pieces);
	}
	cout << result << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~