SDJ( 수돈재 아님 ㅎ )

[C++] 9019 - DSLR 본문

알고리즘/Backjoon

[C++] 9019 - DSLR

ShinDongJun 2020. 1. 23. 12:50

문제 링크 : https://www.acmicpc.net/problem/9019

 

9019번: DSLR

문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자) D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경

www.acmicpc.net

 

 

 

 

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<bits/stdc++.h>
 
#define endl '\n'
 
using namespace std;
 
bool visited[10005];
 
typedef struct Data{
    int reg;
    string command;
}Data;
 
int D(int r);
int S(int r);
int L(int r);
int R(int r);
Data BFS(int A, int B);
 
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int t;
    int A, B;
 
    cin >> t;
 
    while(t--)
    {
        cin >> A >> B;
        cout << BFS(A, B).command << endl;
        memset(visited, 0, sizeof(visited));
    }
 
    return 0;
}
 
int D(int r)
{
    return (2*r)%10000;
}
 
int S(int r)
{
    return (r == 0 ? 9999 : r - 1);
}
 
int L(int r)
{
    int tmp = r/1000;
    r = (10 * r)%10000 + tmp;
    return r;
}
 
int R(int r)
{
    int tmp = r%10;
    r = r/10 + tmp*1000;
    return r;
}
 
Data BFS(int A, int B)
{
    Data ret, tmp;
    int ret_command_size = ret.command.size();
    int tmp_command_size;
    queue<Data> q;
    q.push({A, ""});
 
    int vD;
    int vS;
    int vL;
    int vR;
 
    while(!q.empty())
    {
        tmp = q.front();
        tmp_command_size = tmp.command.size();
        q.pop();
 
        visited[tmp.reg] = true;
        if(tmp.reg == B)
        {
            if(ret_command_size == 0 || tmp_command_size < ret_command_size)
            {
                ret = tmp;
                ret_command_size = tmp_command_size;
            }
        }
        else if(tmp_command_size < ret_command_size || ret_command_size == 0)
        {
            if(visited[vD = D(tmp.reg)] == false)
            {
                visited[vD] = true;
                q.push({vD, tmp.command + "D"});
            }
            if(visited[vS = S(tmp.reg)] == false)
            {
                visited[vS] = true;
                q.push({vS, tmp.command + "S"});
            }
            if(visited[vL = L(tmp.reg)] == false)
            {
                visited[vL] = true;
                q.push({vL, tmp.command + "L"});
            }
            if(visited[vR = R(tmp.reg)] == false)
            {
                visited[vR] = true;
                q.push({vR, tmp.command + "R"});
            }
        }
    }
 
    return ret;
}
저작자표시

'알고리즘 > Backjoon' 카테고리의 다른 글

[C++] 2468 - 안전 영역  (0) 2020.01.23
[C++] 2422 - 한윤정이 이탈리아에 가서 아이스크림을 사먹는데  (0) 2020.01.23
[C++] 1780 - 종이의 개수  (0) 2020.01.23
[C++] 1158 - 요세푸스 문제  (0) 2020.01.23
[C++] 10815 - 숫자 카드  (0) 2020.01.23
'알고리즘/Backjoon' Related Articles more
Comments