-

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

1-1. 삼성 SW 테스트

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

asdklfjlasdlfkj 2020. 1. 15. 17:40

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

 

17825번: 주사위 윷놀이

첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다.

www.acmicpc.net

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

 

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

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

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

 

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

 

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

 

아래는 소스코드 (40ms)

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int answer = -1;
int dice[10];
 
int lookupTable[33][6= {
    { 012345 },
    { 2234510 },
    { 43451011 },
    { 645101112 },
    { 8510111213 },
    { 10678925 },
    { 137892526 },
    { 1689252627 },
    { 19925262732 },
    { 252526273232 },
    { 121112131417 },
    { 141213141718 },
    { 161314171819 },
    { 181417181920 },
    { 20151692526 },
    { 22169252627 },
    { 24925262732 },
    { 221819202128 },
    { 241920212829 },
    { 262021282930 },
    { 282128293031 },
    { 30222324925 },
    { 28232492526 },
    { 27249252627 },
    { 26925262732 },
    { 302627323232 },
    { 352732323232 },
    { 403232323232 },
    { 322930312732 },
    { 343031273232 },
    { 363127323232 },
    { 382732323232 },
    { 03232323232 }
}; // 번째 위치의 점수[0], 갈 수 있는 곳.[1]~[5]
 
void Simulation(int bit){
    int pos[4= { 0000 }; // 각 말의 위치
    int score[4= { 0000 }; // 각 말의 점수
 
    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;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs
 

Comments