9019번: DSLR
네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에
www.acmicpc.net
- 풀이
DSLR 방식을 사용하여 최소의 방법으로 A에서 B의 값을 만들어내면 되는 문제입니다.
- D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.
- S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
- L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.
- R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.
일단 위의 설명대로 하나씩 메소드를 만들어 값을 변경시킬 수 있도록 했습니다.
이제 정확하게 A에서 B로가는 최단명령어를 조사해야합니다. dfs를 사용할 경우 딥하게 들어가 stackoverflow가 발생할 수 있기때문에 bfs방식을 사용했습니다.
방식 ) class를 만들어 랜덤으로 DSLR을 하며 변경된 값과 command를 추가시켜주었습니다.
예외 ) check 배열을 만들어 같은 값이 또 나온 경우 같은 작업을 반복하지 않도록 해주었습니다.
문제에서 원하는 답은 같은 명령어의 길이이면 모두 정답이 되기 때문에 반복문을 통해 가장 먼저 B가 되는 값을 return 시켜주었습니다.
- 코드
import java.io.IOException;
import java.io.InputStream;
import java.util.*;
public class Main {
static StringBuilder sb;
static boolean[] check;
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
SetData();
System.out.println(sb);
}
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
int testcase = in.nextInt();
sb = new StringBuilder();
for(int i = 0; i < testcase; i++) {
int a = in.nextInt();
int b = in.nextInt();
check = new boolean[10000];
sb.append(bfs(a,b)).append("\n");
}
}
private static String bfs(int a, int b) {
Queue<Node> queue = new LinkedList<>();
check[a] = true;
queue.add(new Node(a, ""));
while(!queue.isEmpty()) {
Node node = queue.poll();
if(node.value == b) {
return node.command;
}
int valueAfterCommand = D(node.value);
if(!check[valueAfterCommand]) {
check[valueAfterCommand] = true;
queue.add(new Node(valueAfterCommand, node.command+"D")) ;
}
valueAfterCommand = S(node.value);
if(!check[valueAfterCommand]) {
check[valueAfterCommand] = true;
queue.add(new Node(valueAfterCommand, node.command+"S")) ;
}
valueAfterCommand = L(node.value);
if(!check[valueAfterCommand]) {
check[valueAfterCommand] = true;
queue.add(new Node(valueAfterCommand, node.command+"L")) ;
}
valueAfterCommand = R(node.value);
if(!check[valueAfterCommand]) {
check[valueAfterCommand] = true;
queue.add(new Node(valueAfterCommand, node.command+"R")) ;
}
}
return "";
}
private static int D(int a) {
return (a*2)%10000;
}
private static int S(int a) {
a -=1;
if(a==-1)
return 9999;
else
return a;
}
private static int L(int a) {
int temp = a%1000;
int temp1 = a/1000;
return temp*10+temp1;
}
private static int R(int a) {
int temp = a % 10;
int temp1 = a / 10;
return temp*1000+temp1;
}
}
class Node {
int value;
String command;
public Node(int value, String command) {
this.value = value;
this.command = command;
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}'algorithm' 카테고리의 다른 글
| [BOJ/JAVA] 백준 1939번 : 중량제한 (0) | 2021.10.23 |
|---|---|
| [BOJ/JAVA] 백준 6064번 : 카잉 달력 (0) | 2021.10.23 |
| [BOJ/JAVA] 백준 13023번 : ABCDE (0) | 2021.10.21 |
| [BOJ/JAVA] 백준 1261번 : 알고스팟 (0) | 2021.10.20 |
| [BOJ/JAVA] 백준 2458번 : 키 순서 (0) | 2021.10.19 |
