Suhwanc

문제 링크 : 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

풀이

Bfs 문제입니다!

문제에 나와있듯 가지치기의 방법은 4가지가 있고, 출력에서 최소한의 명령어 나열을 요구했으므로 문제에 나와있는 그대로 bfs탐색을 해주면서 B가 되었을 때 값을 리턴해주면 되겠다.

 

소스

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
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
 
bool c[10001];
 
int cmd_d(int n) {
    if (n * 2 > 9999return (2 * n) % 10000;
    else return (2 * n);
}
int cmd_s(int n) {
    if (n == 0return 9999;
    else return n - 1;
}
int cmd_L(int n) {
    int first = n / 1000;
    int temp = (n % 1000* 10;
    return temp + first;
}
int cmd_R(int n) {
    int last = (n % 10);
    int temp = (n / 10);
 
    return (last * 1000+ temp;
}
int main()
{
    int t; scanf("%d"&t);
    while (t--) {
        int a, b; scanf("%d%d"&a, &b);
        queue<pair<intstring> >q;
        memset(c, falsesizeof(c));
 
        q.push(make_pair(a, ""));
        while (!q.empty()) {
            int num = q.front().first;
            string k = q.front().second;
            
            if (num == b) {
                cout << k << "\n";
                break;
            }
            q.pop();
            int x = cmd_d(num);
            if (c[x] == false) {
                c[x] = true;
                q.push(make_pair(x, k + "D"));
            }
            int y = cmd_s(num);
            if (c[y] == false) {
                c[y] = true;
                q.push(make_pair(y, k + "S"));
            }
            x = cmd_L(num);
            if (c[x] == false) {
                c[x] = true;
                q.push(make_pair(x, k + "L"));
            }
            y = cmd_R(num);
            if (c[y] == false) {
                c[y] = true;
                q.push(make_pair(y, k + "R"));
            }
        }
    }
    return 0;
}
cs

'백준 문제풀이' 카테고리의 다른 글

백준 1248번 맞춰봐  (0) 2020.01.20
백준 15661번 링크와 스타트  (0) 2020.01.20
백준 1697번 숨바꼭질  (0) 2020.01.16
백준 17404 RGB 거리 2  (0) 2020.01.16
백준 1309번 동물원  (0) 2020.01.16