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

 

17825번: 주사위 윷놀이

주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 가장 처음에는 시작에 말 4개가 있다. 말은 게임판에 적힌 화살표의 방향대로만 이동할 수 있다. 파란색 칸에서 말이 이동을 시작하는 경우에는 파란색 화살표의 방향으로 이동해야 하며 파란색 칸을 지나가는 경우에는 빨간 화살표의 방향대로 이동해야 한다. 게임은 1부터 5까지 한 면에 하나씩 적혀있는 5면 주사위를 굴려서 나온 수만큼 이동하는 방식으로 진행한다. 이동하려고 하는 칸에 말이 이미 있는 경우에

www.acmicpc.net

문제설명

백준저지 17825번 문제, 주사위 윷놀이 풀이입니다.

 

문제를 보면 나름 복잡해 보이는 윷놀이 판이 있고, 이 윷놀이 판에서 주사위를 10번 던져서 그 주사위의 눈금값이 고정되어 있을 때, 어떻게 하면 최대 점수를 얻느냐 대략 이런문제입니다.

 

문제에서 설명이 좀 부족한 부분으로는, 윷판에 써잇는 숫자가 그 곳에 오르면 얻게 되는 점수이고, 빨간색 화살표는 기본적으로 이동하는 길입니다. 파란색의 화살표는 파란색 큰 동그라미 위치에 말이 놓였을때 이동하는 경로입니다.

 

윷놀이에 대한 기본적인 규칙은 다들 알 것이라고 생각해서, 해당 부분 설명 부분은 간단하게 한 느낌입니다.

 

 

문제 해결 전략 설정

 

일단 말이 4가지가 있고 각 10번의 이동 중 각각 이동마다 1,2,3,4번 말 중 어떤 말을 움직일지를 결정해야 합니다.

 

10번마다 독립적인 4가지의 선택지가 있고, 따라서 총 결정할 수 있는 방법은 //(4^{10}//)이 되겠습니다.

 

이 값은 //(2^{20}//)의 값과 동일하며, //((2^{10})^{2} = 1024^2 = 1048576//)입니다.

 

100만정도 되는 양으로 1초안에 충분히 계산할 수 있는 계산량입니다. 보통 1억번 연산에 1초로 생각하시면 편합니다.

 

따라서 모든 경우의 수를 다 따져보아도 충분히 풀리는 문제이므로, 완전탐색으로 해결할 수 있습니다.

 

구현전략

말의 개수가 4가지이고, 10개의 독립적인 선택지를 고르는 방식이므로, 이러한 경우 비트마스킹(bitmasking)을 이용해서 구현하면 편리합니다.

 

비트는 0과 1로 바이너리(2가지)이지만, 2비트를 사용하면 00,01,10,11로 4가지를 표현할 수 있습니다. 따라서 2*10=20 비트만 사용하면 해당 경우의 수를 모두 표현할 수 있습니다.

 

모든 경우의 수를 모두 순회하는 방식은 비트마스킹을 이용한다고 할 때, 각각의 윷놀이 말이 움직이는 것을 시뮬레이션을 해서 점수를 구해야 합니다.

 

윷 판의 형태가 규칙성을 찾기 힘든 형태이지만, 총 33개 칸에 주사위가 1~5의 숫자만 나오므로 룩업테이블(look-up table)을 사용할 만 합니다.

 

아래와 같이 그림을 그려서 룩업 테이블을 구성해 보았습니다.

 

빨간색은 칸에 부여한 번호이고, 노란색은 칸에서 얻는 점수입니다.

 

코드

구현한 코드입니다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int dice[10];
#define END 32

//이동 규칙이 복잡할 수 있으므로 Look-up 테이블을 만들어서 사용한다.
//jump[index][0] = 해당 판 점수
//jump[index][1~5] => 주사위 해당 수가 나오면 이동하는 양
int jump[33][6] = {
	{0,1,2,3,4,5}, //0번자리
	{2,2,3,4,5,9}, //1번자리
	{4,3,4,5,9,10}, //2번자리
	{6,4,5,9,10,11}, //3번자리
	{8,5,9,10,11,12},//4번자리
	{10,6,7,8,20,29},//5번자리
	{13,7,8,20,29,30}, //6번자리
	{16,8,20,29,30,31}, //7번자리
	{19,20,29,30,31,32}, //8번자리
	{12,10,11,12,13,14}, //9번자리
	{14,11,12,13,14,15}, //10번자리
	{16,12,13,14,15,16}, //11번자리
	{18,13,14,15,16,17}, //12번자리
	{20,18,19,20,29,30}, //13번자리
	{22,15,16,17,24,25}, //14번자리
	{24,16,17,24,25,26}, //15번자리
	{26,17,24,25,26,27}, //16번자리
	{28,24,25,26,27,28}, //17번자리
	{22,19,20,29,30,31}, //18번자리
	{24,20,29,30,31,32}, //19번자리
	{25,29,30,31,32,32}, //20번자리
	{26,20,29,30,31,32}, //21번자리
	{27,21,20,29,30,31}, //22번자리
	{28,22,21,20,29,30}, //23번자리
	{30,23,22,21,20,29}, //24번자리
	{32,26,27,28,31,32}, //25번자리
	{34,27,28,31,32,32}, //26번자리
	{36,28,31,32,32,32}, //27번자리
	{38,31,32,32,32,32}, //28번자리
	{30,30,31,32,32,32}, //29번자리
	{35,31,32,32,32,32}, //30번자리
	{40,32,32,32,32,32}, //31번자리
	{0,32,32,32,32,32} //32번자리
};
int ans;
void check(int bit) {
	int score = 0;
	int occupation[35];
	int pos[4];
	memset(occupation, 0, sizeof(occupation));
	memset(pos, 0, sizeof(pos));
	occupation[0] = 4;

	for (int turn = 0; turn < 10; turn++) {
		//이번에 옮길 말
		int horse = (bit >> (turn * 2)) & 0x3;

		//이동하는 거리
		int move = dice[turn];

		//현재 위치
		int& current_pos = pos[horse];

		//이동할 위치
		int next_pos = jump[current_pos][move];

		//이번 이동으로 얻을 점수
		int get_score = jump[next_pos][0];

		//처음이나 끝 위치가 아닌데 말이 겹치는 경우
		if (occupation[next_pos] > 0 && next_pos && next_pos != END) {
			//불가능한 이동
			return;
		}
		else {
			score += get_score;
			occupation[next_pos]++;
			occupation[current_pos]--;
			current_pos = next_pos;
		}
	}
	ans = max(ans, score);
}
int main() {
	for (int i = 0; i < 10; i++)
		cin >> dice[i];
	for (int bit = 0; bit < (1 << 20); bit++) {
		check(bit);
	}
	cout << ans << endl;

}

+ Recent posts