88. DSLR (백준 9019) [JAVA]

 

문제

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

9019번: DSLR

시간제한	메모리제한	제출	정답	맞은 사람	정답 비율
6초	256MB	32024	8174	5083	22.072%

문제

네 개의 명령어 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로 변환하기 위해 필요한 최소한의 명령어 나열을 출력한다. 가능한 명령어 나열이 여러가지면, 아무거나 출력한다.

 

풀이

D,S,L,R에 해당하는 계산이 까다롭기 때문에, 규칙을 수학적으로 생각해서는 정답을 도출해내기가 어렵다.

그렇다면, 결국 모든 경우의 수를 고려해야 하는데 - 완전탐색 + DP로 생각했다.

완전탐색을 그럼 어떻게 해야 할까 고민하다, 각각의 숫자를 노드로 생각하여 BFS를 통해 방문하는 방법을 생각했다.

수의 범위가 0~9999이기 때문에 배열을 통해 좌표를 저장할만하였다.

처음에는 배열 값에 방문여부가 아닌 그동안의 연산기록을 저장하려 하였으나, 그럴 경우 마지막에 정답이 꼬여서 DNA라는 필드를 통해 본인의 방문여부를 저장하도록 하였다.

String을 사용하면 뭔가 메모리를 너무 많이 잡아먹을 것 같아서 정수형으로 저장하고 마지막에 치환하는 방식을 사용하였는데,

이때 0 - 1000과 같은 경우 DNA가 정수형의 저장범위를 넘어서버려서 long으로 바꿔서 해봤다.

long까지는 되는 거 보니 정답이 19자리는 넘지 않나 보다.

 

코드

import java.io.*;
import java.util.*;

public class Main {

    static int T;
    static int[] stt;
    static int[] des;
    static String[] ans;

    //D : 2n mod 10000;
    //S : n-1 (if 0 -> 9999)
    //L : left rotat (0004 -> 0040)
    //R : right rotat (0004 -> 4000)    
    //무지성 DSLR 대입?

    public static void main(String[] args) throws IOException{
        StringTokenizer st;
        BufferedReader br = new java.io.BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        T = Integer.parseInt(st.nextToken());

        stt = new int[T];
        des = new int[T];
        ans = new String[T];

        for(int i=0; i<T; i++) {
            st = new StringTokenizer(br.readLine());
            stt[i] = Integer.parseInt(st.nextToken());
            des[i] = Integer.parseInt(st.nextToken());
        }

        for(int i=0; i<T; i++) {
            BFS(i);
            System.out.println(ans[i]);
        }
    }


    public static void BFS(int round) throws IOException {    
        //0~9999;
        int[] map = new int[10000];
        Queue<path> q = new LinkedList<>();

        q.add(new path(stt[round], 0));
        map[stt[round]] = 1;

        int nextVal = 0;
        while(!q.isEmpty()) {
                path cur = q.poll();
                //System.out.println(cur.value + " " + cur.dna);

                //종료조건
                if(cur.value == des[round]) {
                    ans[round] = mapping(cur.dna);
                    return;
                }

                nextVal = D(cur.value);
                //방문안함
                if(map[nextVal] == 0) {
                    map[nextVal] = 1;
                    q.add(new path(nextVal, cur.returnDna(1)));
                }

                nextVal = S(cur.value);
                if(map[nextVal] == 0) {
                    map[nextVal] = 1;
                    q.add(new path(nextVal, cur.returnDna(2)));
                }

                nextVal = L(cur.value);
                if(map[nextVal] == 0) {
                    map[nextVal] = 1;
                    q.add(new path(nextVal, cur.returnDna(3)));
                }

                nextVal = R(cur.value);
                if(map[nextVal] == 0) {
                    map[nextVal] = 1;
                    q.add(new path(nextVal, cur.returnDna(4)));
                }
        }
    }

    public static String mapping(long answer) {
        return Long.toString(answer)
                .replaceAll("1", "D")
                .replaceAll("2", "S")
                .replaceAll("3", "L")
                .replaceAll("4", "R");
    }


    public static int D(int val) {
        return (2*val) % 10000;
    }

    public static int S(int val) {
        return (val+9999) % 10000;
    }

    public static int L(int val) {
        return (val*10) % 10000 + (val/1000);
    }

    public static int R(int val) {
        return (val/10) + (val%10)*1000;
    }    
}

class path{
    int value;
    long dna = 0;

    public path(int val, long d) {
        this.value = val;
        this.dna = d;
    }

    public long returnDna(int opr) {
        return dna*10 + opr;
    }
}

 

결과