[백준/BOJ] 백준 17825번 : 주사위 윷놀이

www.acmicpc.net/problem/17825

17825번: 주사위 윷놀이

각각의 지점들을 board에 표시하고, 각각의 지점에서 움직이는 것을 고려하여 Move함수를 만들었다. 그리고 말들을 움직이는 경우를 모두 확인하여 점수의 최댓값을 구한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int board[33];
vector<int> moving;
vector<int> horse(4, 0);
vector<int> finish_horse(4, 0);

void Pre()
{
	for (int i = 0; i <= 20; i++)
		board[i] = 2 * i;

	board[21] = 13;
	board[22] = 16;
	board[23] = 19; //4거리 직전

	board[24] = 22;
	board[25] = 24; //4거리 직전

	board[26] = 28;
	board[27] = 27;
	board[28] = 26; //4거리 직전

	board[29] = 25; //4거리

	board[30] = 30;
	board[31] = 35; //도착 직전의 직전(도착 직전은 board[20])

	board[32] = 0; //도착
}

//this_horse를 moving_num만큼 옮겼을때의 점수
int Move(int this_horse, int moving_num)
{
	int here = horse[this_horse];
	int there = here;

	for (int j = 0; j < moving_num; j++)
	{
		if (here == 23 || here == 25 || here == 28)
			there = 29;

		else if (here == 31)
			there = 20;

		else if (here == 20)
			there = 32;

		else
			there++;

		if (j == 0)
		{
			if (here == 5)
				there = 21;

			if (here == 10)
				there = 24;

			if (here == 15)
				there = 26;
		}

		if (there == 32)
		{
			finish_horse[this_horse] = 1;

			break;
		}

		here = there;
	}

	if ((there != 32) && (horse[0] == there || horse[1] == there || horse[2] == there || horse[3] == there))
		return -987654321;

	horse[this_horse] = there; //this_horse가 there로 옮겨짐

	return board[there];
}

int Solve(int cnt, int sum)
{
	if (cnt == 10)
		return sum;

	int result = -987654321;
	int this_add;

	for (int i = 0; i < 4; i++)
	{
		int this_horse_original = horse[i];
		int this_horse_finished_original = finish_horse[i];

		if (this_horse_finished_original == 1)
			continue;

		this_add = Move(i, moving[cnt]);

		if (this_add != -987654321)
		{
			result = max(result, Solve(cnt + 1, sum + this_add));
		}

		//원상 복귀
		horse[i] = this_horse_original;
		finish_horse[i] = this_horse_finished_original;
	}

	return result;
}

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

	for (int i = 0; i < 10; i++)
	{
		int input;
		cin >> input;

		moving.push_back(input);
	}

	Pre();
	cout << Solve(0, 0);
}