[삼성SW테스트] 백준 17825번 - 주사위 윷놀이 (정답률 30%)

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

17825번: 주사위 윷놀이

2019년 하반기 삼성 SW 테스트 기출문제다. (유형: 브루트포스)

 

주사위 10개의 눈이 주어지고, 말이 4개가 존재한다.

주사위 눈 하나당 말 4개의 경우가 있으므로 총 4^10 경우의 수가 존재한다.

이는 약 1백만이므로 충분히 브루트포스를 사용해도 된다.

 

나는 비트 연산을 통해 풀었다. 말이 4개이므로 00, 01, 10, 11로 표현할 수 있는데, 총 10개의 눈이므로 2 x 10 비트가 필요하다. 이는 for문과 비트 shift 연산을 통해 쉽게 구현할 수 있다.

 

또한 룩업테이블을 노가다스럽긴하지만 구현하여 활용하였다.

 

아래는 소스코드 (40ms)

 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int answer = -1;
int dice[10];
 
int lookupTable[33][6] = {
    { 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, 32 },
    { 25, 25, 26, 27, 32, 32 },
    { 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, 32 },
    { 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, 32 },
    { 30, 26, 27, 32, 32, 32 },
    { 35, 27, 32, 32, 32, 32 },
    { 40, 32, 32, 32, 32, 32 },
    { 32, 29, 30, 31, 27, 32 },
    { 34, 30, 31, 27, 32, 32 },
    { 36, 31, 27, 32, 32, 32 },
    { 38, 27, 32, 32, 32, 32 },
    { 0, 32, 32, 32, 32, 32 }
}; // 번째 위치의 점수[0], 갈 수 있는 곳.[1]~[5]
 
void Simulation(int bit){
    int pos[4] = { 0, 0, 0, 0 }; // 각 말의 위치
    int score[4] = { 0, 0, 0, 0 }; // 각 말의 점수
 
    int count[33]; // 각 위치당 말의 개수
    for (int i = 0; i < 33; i++) count[i] = 0;
    count[0] = 4;
    
    for (int i = 0; i < 10; i++){
        int cur_horse = bit & 3; // 현재 말의 인덱스.
        bit >>= 2;
        int cur_dice = dice[i]; // 몇 칸 가?
        int curpos = pos[cur_horse]; // 현재 말의 위치.
        int nextpos = lookupTable[curpos][cur_dice];
        int whatscore = lookupTable[nextpos][0];
 
        if (nextpos != 0 && nextpos != 32 && count[nextpos] > 0){
            return;
        }
        else{
            // 갈 수 있으면 가.
            count[curpos]--;
            count[nextpos]++;
            pos[cur_horse] = nextpos;
            score[cur_horse] += whatscore;
        }
    }
    int sum = 0;
    for (int i = 0; i < 4; i++) sum += score[i];
    answer = max(answer, sum);
}
 
int main(){
    for (int i = 0; i < 10; i++) cin >> dice[i];
    for (int bit = 0; bit < (1 << 20); bit++){
        Simulation(bit);
    }
    cout << answer << '\n';
    return 0;
}