1. 문제
https://www.acmicpc.net/problem/9019
2. 적용할 알고리즘
큐에 명령을 사용한 순서를 string으로 저장하고 bfs를 돌리면 될 것 같다
3. 풀이
큐에서 숫자를 뽑아내 다음 숫자를 선택하는 연산을 그 때 마다 수행하니 시간 초과가 났다.
따라서 res[i][j] 이차원 배열에 숫자 i에서 연산을 하여 나오는 숫자를 j(0, 1, 2, 3)에 미리 저장해놓고
테스트케이스마다 저장해놓은 정보를 가져다 쓰기만 하면 시간을 줄일 수 있다.
시간 제한이 좀 애매하긴 했다. 고작 1/4 줄인다고 해결될 것 같지 않아서 이 방식을 생각하지 않은 것 같다.
테스트 케이스가 여러 개 주어지는 문제에서 미리 필요한 정보를 계산해놓고 정보를 가져다 쓰는 방식을 사용하여 시간을 줄일 수 있다는 걸 기억하자.
4, 코드
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<tuple>
using namespace std;
typedef long long ll;
string vis[10005];
int FuncD(int num)
{
return num * 2 % 10000;
}
int FuncS(int num)
{
if (num == 0) num = 9999;
else num--;
return num;
}
int FuncL(int num)
{
return (num % 1000) * 10 + num / 1000;
}
int FuncR(int num)
{
return (num % 10) * 1000 + num / 10;
}
int res[10005][4];
char c[4] = { 'D', 'S', 'L', 'R' };
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
for (int i = 0; i <= 9999; i++)
{
res[i][0] = FuncD(i);
res[i][1] = FuncS(i);
res[i][2] = FuncL(i);
res[i][3] = FuncR(i);
}
while (t--)
{
vector<bool> vis(10005);
int a, b;
cin >> a >> b;
string s;
queue<pair<int, string>> Q;
Q.push({ a, "" });
vis[a] = 1;
while (!Q.empty())
{
int cn;
string cs;
tie(cn, cs) = Q.front(); Q.pop();
if (cn == b)
{
cout << cs << '\n';
break;
}
for (int i = 0; i < 4; i++)
{
int nn = res[cn][i];
string ns = cs;
if (vis[nn]) continue;
ns.push_back(c[i]);
Q.push({ nn, ns });
vis[nn] = 1;
}
}
}
}