Easy is Perfect

[백준] 9019번 C/C++ 풀이 _ DSLR

  • melonicedlatte
  • Sep 05, 2018


출처 : https://www.acmicpc.net/problem/9019 

DSLR 성공스페셜 저지

시간 제한메모리 제한제출정답맞은 사람정답 비율
6 초128 MB102532440150921.588%

문제

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

  1. D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.
  2. S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
  3. L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.
  4. R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.

위에서 언급한 것처럼, L 과 R 명령어는 십진 자릿수를 가정하고 연산을 수행한다. 예를 들어서 n = 1234 라면 여기에 L 을 적용하면 2341 이 되고 R 을 적용하면 4123 이 된다.

여러분이 작성할 프로그램은 주어진 서로 다른 두 정수 A와 B(A ≠ B)에 대하여 A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램이다. 예를 들어서 A = 1234, B = 3412 라면 다음과 같이 두 개의 명령어를 적용하면 A를 B로 변환할 수 있다.

1234 →L 2341 →L 3412
1234 →R 4123 →R 3412

따라서 여러분의 프로그램은 이 경우에 LL 이나 RR 을 출력해야 한다.

n의 자릿수로 0 이 포함된 경우에 주의해야 한다. 예를 들어서 1000 에 L 을 적용하면 0001 이 되므로 결과는 1 이 된다. 그러나 R 을 적용하면 0100 이 되므로 결과는 100 이 된다.

입력

프로그램 입력은 T 개의 테스트 케이스로 구성된다. 테스트 케이스 개수 T 는 입력의 첫 줄에 주어진다. 각 테스트 케이스로는 두 개의 정수 A와 B(A ≠ B)가 공백으로 분리되어 차례로 주어지는데 A는 레지스터의 초기 값을 나타내고 B는 최종 값을 나타낸다. A 와 B는 모두 0 이상 10,000 미만이다.

출력

A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 출력한다.

예제 입력 1 

3
1234 3412
1000 1
1 16

예제 출력 1 

LL
L
DDDD

출처

ACM-ICPC > Regionals > Asia > Korea > Nationwide Internet Competition > Asia Regional - Daejeon Nationalwide Internet Competition 2011 D번

알고리즘 분류





























풀이


이 문제는 BFS 를 사용하여 정답을 만나기만 하면 해당 글자를 출력하면 최소 글자가 나오게 됩니다. 

이 문제는 자꾸 시간초과가 나왔습니다. 
이유는 string을 각각의 트리 노드에 하나하나씩 저장했는데, string의 사용으로 인하여 시간초과가 발생했습니다. 

다른 소스코드를 구글링 해서 보면 string 자체가 연산이 비싼 것도 있지만 기존에 있던 값들을 복사해서 새로 넣어줘야 되는 점도 시간을 더해 주는 것에 한 몫을 하고 있습니다. 

http://mrl.kr/boj9019/ 
이 링크에서 푼 풀이처럼 parent 를 뭔지 기록하는 방법을 사용하면 훨씬 더 빠른 시간 내에 풀 수 있습니다. 

위와 같은 그림처럼 parent 를 표시하고 정답을 만나면 parent 를 계속 추적하여 답을 찾는 방법입니다.

위의 링크를 참조하시면 부모를 기록하는 풀이를 확인할 수 있습니다. 


아래의 방법은 제가 푼 방법입니다. 


부모를 기록하지 않고 통과한 소스코드

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
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#define REGISTER 4
using namespace std;
 
typedef struct NODE {
    int num_;
    string regi_use_;
}BFS_Q;
 
int main(){
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) {
        int A, B;  cin >> A >> B;
        int is_end = 0;
        queue<NODE> bfs_queue;
        vector<int> is_visited(10000, 0);
        bfs_queue.push({ A, "" }); 
        while (bfs_queue.size() && is_end == 0) {
            NODE now_node = bfs_queue.front();  bfs_queue.pop(); 
 
            // 방문 여부 확인 
            if (is_visited[now_node.num_]) continue;
            is_visited[now_node.num_] = 1; 
 
            // 정답이면 while 탈출~
            if (now_node.num_ == B) {
                cout << now_node.regi_use_ << "\n";
                break;
            } 
 
            int jari_1000_to_1, jari_1_to_1000;
 
            // 레지스터 별 동작 조정 
            for (int register_idx = 0; register_idx < REGISTER; register_idx++)  {
                NODE new_node = {0, now_node.regi_use_ };
                switch (register_idx) {
                case 0:
                    new_node.num_ = (now_node.num_ * 2) % 10000; 
                    new_node.regi_use_ += "D"; 
                    break;
                case 1:
                    new_node.num_ = (now_node.num_ == 0 ? 9999 : now_node.num_ - 1);
                    new_node.regi_use_ += "S";
                    break;
                case 2:
                    jari_1000_to_1 = now_node.num_ / 1000;
                    new_node.num_ = (now_node.num_ % 1000) * 10 + jari_1000_to_1;
                    new_node.regi_use_ += "L";
                    break;
                case 3:
                    jari_1_to_1000 = now_node.num_ % 10;
                    new_node.num_ = (now_node.num_ / 10) % 1000 + jari_1_to_1000 *1000;
                    new_node.regi_use_ += "R";
                    break;
                }
 
                if (!is_visited[new_node.num_]){
                    if (new_node.num_ == B) { 
                        cout << new_node.regi_use_ << "\n";
                        is_end = 1;
                        break;
                    }
                    bfs_queue.push(new_node);
                }
            }
        }
    }
    return 0;
}
cs



느려서 시간초과인 코드

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
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#define REGISTER 4
using namespace std;
 
typedef struct NODE {
    int num_;
    string regi_use_;
}BFS_Q;
 
int main(){
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) {
        int A, B;  cin >> A >> B;
        int is_end = 0;
        queue<NODE> bfs_queue;
        vector<int> is_visited(10000, 0);
        bfs_queue.push({ A, "" }); 
        while (bfs_queue.size() && is_end == 0) {
            NODE now_node = bfs_queue.front();  bfs_queue.pop(); 
 
            // 방문 여부 확인 
            if (is_visited[now_node.num_]) continue;
            is_visited[now_node.num_] = 1; 
 
            // 정답이면 while 탈출~
            if (now_node.num_ == B) {
                cout << now_node.regi_use_ << "\n";
                break;
            }
 
            string num_string;
            if (now_node.num_< 10)
                num_string = "000" + to_string(now_node.num_);
            else if (now_node.num_<100)
                num_string = "00" + to_string(now_node.num_);
            else if (now_node.num_<1000)
                num_string = "0" + to_string(now_node.num_);
            else
                num_string = "" + to_string(now_node.num_);
 
            // 레지스터 별 동작 조정 
            for (int register_idx = 0; register_idx < REGISTER; register_idx++)  {
                NODE new_node = {0, now_node.regi_use_ };
                switch (register_idx) {
                case 0:
                    new_node.num_ = (now_node.num_ * 2) % 10000; 
                    new_node.regi_use_ += "D"; 
                    break;
                case 1:
                    new_node.num_ = (now_node.num_ == 0 ? 9999 : now_node.num_ - 1);
                    new_node.regi_use_ += "S";
                    break;
                case 2:
                    new_node.num_ = (num_string[0] - '0') + (num_string[1] - '0') * 1000 + (num_string[2] - '0') * 100 + (num_string[3] - '0') * 10;
                    new_node.regi_use_ += "L";
                    break;
                case 3: 
                    new_node.num_ = (num_string[0] - '0') * 100 + (num_string[1] - '0') * 10 + (num_string[2] - '0') + (num_string[3] - '0') * 1000;
                    new_node.regi_use_ += "R";
                    break;
                }
 
                if (!is_visited[new_node.num_]){
                    if (new_node.num_ == B) { 
                        cout << new_node.regi_use_ << "\n";
                        is_end = 1;
                        break;
                    }
                    bfs_queue.push(new_node);
                }
            }
        }
    }
    return 0;
}
cs




Search