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;
}
'알고리즘 & Problem Solving' 카테고리의 다른 글
백준 2529번 부등호 문제 풀이 (0) | 2019.11.12 |
---|---|
백준 9663번 문제 N-Queen 문제 풀이 (0) | 2019.11.04 |
백준 17822번 원판 돌리기 문제 풀이 (3) | 2019.10.23 |
Google Kickstart Round G 2019 후기 (2) | 2019.10.20 |
백준 14501번 퇴사 문제 풀이 (0) | 2019.09.27 |