[9019번] 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 이 된다.

[예제입력]

(첫 줄에 Test Case 수 T가 주어진다)

3

1234 3412

1000 1

1 16

[예제출력]

LL

L

DDDD

[풀이를 위한 개념]

http://twoearth.tistory.com/3?category=809135 (숨바꼭질) 문제에서 사용하는 BFS를 참조하시길 바랍니다.

BFS 는 다음과 같은 문제에 사용되는 알고리즘입니다.

1. 최소 상태의 개수가 충분히 작다.

2. 최소비용을 구하는 문제

3. 이동간극(비용)이 1로 동일해야 한다.

위의 조건을 충족하므로 BFS를 사용하여 구하는 것이 수월합니다.

출력은 string 형태로 나오므로 string 배열을 통해 방문하는 nod에 방문할 때마다 연산된 'D', 'S', 'L', 'R'의 char 자료형을 모두 더해줍니다.

string 은 쉽게 + 연산이 가능합니다.

예를들어 1234 수를 만드는데 'D'의 연산을 사용했다면 string[1234] = string[그 전까지 사용했던 연산들] + 'D' 와 같이 사용가능합니다.

[풀이과정]

각 연산에 대해서 함수를 쓰기 편하게 만들어 놓고 사용하는 것이 좋습니다.

D : 현재 숫자에서 x2를 하고 결과값이 10000을 넘어갈 경우 10000을 나눈 나머지 값으로 연산됩니다. 간단하게 생각해보면  결과값이 10000보다 작든 크든 %10000을 취해주면 모든 조건을 만족하게 됩니다. 현재 숫자가 n일 때, (n*2)%10000으로 표현할 수 있습니다.

S : 현재 숫자에서 -1을 하고 현재값이 0일 경우 음수가 나오므로 10000에서 1을 뺀 9999을 출력합니다. 현재 숫자가 n일 때,  n == 0 ? n = 10000 : n 으로 계산할 수 있습니다..

L : 자릿수를 왼쪽으로 이동하므로 맨 왼쪽에 있는 숫자를 1의 자리 숫자로 바꿔주고, 나머지 숫자들은 x10을 해준 뒤 더해주면 됩니다. 현재 숫자가 n일 때, n/1000 + (n%1000)*10으로 계산할 수 있습니다.

R : 자릿수를 오른쪽으로 이동하므로 맨 오른쪽에 있는 숫자를 1000의 자리 숫자로 바꿔주고, 나머지 숫자들은 /10을 해준 뒤 더해주면 됩니다. 현재 숫자가 n일 때, (n%10)*1000 + (n/10)

이렇게 함수로 모두 만들어 놓고 모든 nod에 네가지의 갈래길을 만들면 됩니다.

[그림1] 미리 만들어 놓은 'D', 'S', 'L', 'R' 연산으로 계산해 나가면서 트리를 만든다.

[정답]

#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
 
using namespace std;
 
int D(int n)    //D연산
{
    return (n*2)%10000;
}
 
int S(int n)    //S연산
{
    int temp;
    n == 0 ? temp = 10000 : temp = n;
    return temp - 1;
}
 
int L(int n)    //L연산
{
    int temp = (n%1000)*10;
    return temp + n/1000;
}
 
int R(int n)    //R연산
{
    int temp = (n%10)*1000;
    return temp + n/10;
}
 
 
string bfs(int now, int result)
{
 
    int next;
    queue<int> q;
    string s[10000] = {"\0"};    //대입돼서 바뀌는 데이터가 아닌 건 항상 초기화 해주자(string형은 null로 초기화 해주는게 좋다
    int visited[10000] = {0};
 
    q.push(now);
    visited[now] = 1;            //시작하는 점은 항상 visited = 1(이미 방문)
 
    while(!q.empty())
    {
        now = q.front();
        q.pop();
 
        //cout << now << endl;
 
        if(now == result)
        {
            break;
        }
 
        if(visited[D(now)] == 0)
        {
            next = D(now);
            q.push(next);
            s[next] = s[now] + 'D';        //s 배열에 지금까지의 연산방법을 계속 추가
            visited[next] = 1;
        }
 
        if(visited[S(now)] == 0)
        {
            next = S(now);
            q.push(next);
            s[next] = s[now] + 'S';
            visited[next] = 1;
        }
 
        if(visited[L(now)] == 0)
        {
            next = L(now);
            q.push(next);
            s[next] = s[now] + 'L';
            visited[next] = 1;
        }
        if(visited[R(now)] == 0)
        {
            next = R(now);
            q.push(next);
            s[next] = s[now] + 'R';
            visited[next] = 1;
        }
 
 
    }
    return s[result];
 
}
 
int main()
{
    int A,B;
    int T;
 
    scanf("%d", &T);
 
    while(T--)
    {
        scanf("%d", &A);
        scanf("%d", &B);
 
        cout << bfs(A,B) <<endl;
    }
}

Two Earth_)

궁금한건 질문해주시고 틀린부분은 지적해주시면 감사하겠습니다 

1. 처음에는 'D'와 'S' 연산을 string[]에 숫자 하나씩 넣은 뒤, 위치를 바꿔주는 형식으로 작성했다.

string toString(int n)

{string s = to_string(n);

if(s.length() < 4)

while(s.length() < 4)

s = '0' + s;

return s;} 와 같은 함수로 1~999 까지는 앞에 '0'을 추가해 네자리 string 배열을 모두 채우고 string으로 모든 계산을 마친 뒤

stoi(toString())으로 int형 숫자로 출력했다. (stoi는 string to int 함수, to_string은 int to string 함수)

여기까진 괜찮았으나... 자리를 바꿔주려면 또 한번의 반복문이 필요하고, n^2의 시간복잡도를 갖는다. 0~9999의 데이터, 만개를 가지고 있고 이것의 제곱이라면 1억이므로 시간초과가 날 수 있다.

0'을 빼고 출력해보면 null 값이 들어가 있는데 이유를 모르겠다.)