아인스트라세의 SW 블로그

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

문제설명

백준저지 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;

}