[Baekjoon] DSLR

👀 문제 설명

문제

네 개의 명령어 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

 

✍🏻풀이

[틀린 풀이] time-out, memory-out

먼저 D, S, L, R 연산을 해주는 함수를 따로 만들었다. D와 S는 쉽게 구현 가능하고, L과 R은 덱을 사용해서 연산을 해줬다. (문제는 이렇게 할 경우 메모리 초과가 난다는 것..^^)

그리고 queue를 사용해 BFS를 돌려준다. 큐에는 { 현재 A값, 현재까지의 명령어 } 쌍으로 저장한다.

큐가 비어있지 않을 동안 DSLR 연산을 각각 하고, 큐에 넣는다. 그리고 큐에서 빼온 '현재 A값'이 B와 같으면 '명령어'를 출력하고 함수를 끝내는 식으로 풀었다.

먼저 내 코드가 틀린 첫 번째 이유는 덱을 사용해 연산을 할 경우 메모리 초과가 날 수 있고, visit 배열을 사용하지 않았다는 점..

visit 배열을 사용해 현재 A값이 이전에도 나왔던 값인지 확인하고, 큐에 넣을지 말지 결정해야 하는데 나는 이 부분을 안했다.

결과는 메모리 초과, 시간 초과 둘 다 났다.

 

[정답]

일단 L과 R 연산은 덱을 사용하지 않고, 나머지 연산을 통해 쉽게 구할 수 있다..^^!

그리고 visited 배열을 사용해 새로 만들어진 A 값이 이전에도 나왔던 값인지 확인하고, 이전에도 나왔던 값이라면 큐에 넣지 않는다.

 

코드

정답

//  DSLR (https://www.acmicpc.net/problem/9019)

#include <iostream>
#include <queue>
#include <cstring>

#define MAX 10001

using namespace std;

int visited[MAX];

string solve(int A, int B) {
    queue<pair<int, string>> Q;
    memset(visited, 0, sizeof(visited));

    Q.push({ A, "" });
    visited[A] = 1;

    while (!Q.empty()) {
        int curA = Q.front().first;
        string curCommand = Q.front().second;
        Q.pop();

        if (curA == B) // 변환한 A가 B와 같으면, while문을 빠져나온다. 
            return curCommand;

        // curA가 아직 B와 같지 않을 경우
        // D
        int nextA = (2 * curA) % 10000;
        if (!visited[nextA]) {
            visited[nextA] = 1;
            Q.push({ nextA, curCommand + 'D' });
        }
        
        // S
        if (curA == 0)
            nextA = 9999;
        else
            nextA = curA - 1;
        if (!visited[nextA]) {
            visited[nextA] = 1;
            Q.push({ nextA, curCommand + 'S' });
        }
        
        // L
        nextA = (curA % 1000) * 10 + (curA / 1000);
        if (!visited[nextA]) {
            visited[nextA] = 1;
            Q.push({ nextA, curCommand + 'L' });
        }

        // R
        nextA = (curA % 10) * 1000 + (curA / 10);
        if (!visited[nextA]) {
            visited[nextA] = 1;
            Q.push({ nextA, curCommand + 'R' });
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);

    int T;
    cin >> T;

    for (int test_case = 0; test_case < T; test_case++) {
        int A, B;
        cin >> A >> B;
        
        cout << solve(A, B) << "\n";
    }

    return 0;
}

 

틀린 답

 

//  DSLR (https://www.acmicpc.net/problem/9019)

#include <iostream>
#include <deque>
#include <queue>

#define MAX 10001

using namespace std;

int functionD(int curA) {
    return (2 * curA) % 10000;
}

int functionS(int curA) {
    if (curA == 0)
        return 9999;
    else
        return curA - 1;
}

/**
 * 덱(deque) 사용
 */
int functionL(int curA) {
    string str = to_string(curA);
    deque<char> DQ;
    for (int i = 0; i < str.length(); i++) {
        DQ.push_back(str[i]);
    }

    char first = DQ.front(); DQ.pop_front();
    DQ.push_back(first);

    string answer = "";
    while (!DQ.empty()) {
        answer += DQ.front(); DQ.pop_front();
    }

    return stoi(answer);
}

int functionR(int curA) {
    string str = to_string(curA);
    deque<char> DQ;
    for (int i = 0; i < str.length(); i++) {
        DQ.push_back(str[i]);
    }

    char end = DQ.back(); DQ.pop_back();
    DQ.push_front(end);

    string answer = "";
    while (!DQ.empty()) {
        answer += DQ.front(); DQ.pop_front();
    }

    return stoi(answer);
}

void solve(int A, int B) {
    queue<pair<int, string>> Q;
    int visited[MAX];

    Q.push({ A, "" });
    visited[A] = 1;
    while (!Q.empty()) {
        int curA = Q.front().first;
        string curCommand = Q.front().second;
        Q.pop();

        if (curA == B) { // 변환한 A가 B와 같으면, while문을 빠져나온다. 
            cout << curCommand << "\n";
            return;
        }

        // curA가 아직 B와 같지 않을 경우
        // D
        if (!visited[functionD(curA)]) {
            visited[functionD(curA)] = 1;
            Q.push({ functionD(curA), curCommand + 'D' });
        }
        
        // S
        if (!visited[functionS(curA)]) {
            visited[functionS(curA)] = 1;
            Q.push({ functionS(curA), curCommand + 'S' });
        }
        
        // L
        if (!visited[functionL(curA)]) {
            visited[functionL(curA)] = 1;
            Q.push({ functionL(curA), curCommand + 'L' });
        }

        // R
        if (!visited[functionR(curA)]) {
            visited[functionR(curA)] = 1;
            Q.push({ functionR(curA), curCommand + 'R' });
        }
    }
}

int main() {
    int T;
    cin >> T;

    for (int test_case = 0; test_case < T; test_case++) {
        int A, B;
        cin >> A >> B;
        
        solve(A, B);
    }

    return 0;
}