DSLR (feat. 백준, 9019번)

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

9019번: DSLR

 

반응형

 

// woohyeon.kim
#include <iostream>
#include <queue>
using namespace std;
inline int calc_D(register int n) {
	return (n << 1) % 10000;
}
inline int calc_S(register int n) {
	if (n == 0)
		n = 9999;
	else
		n -= 1;
	return n;
}
inline int calc_L(register int n) {
	register int d1 = n / 1000;
	register int d2 = (n % 1000) / 100;
	register int d3 = (n % 100) / 10;
	register int d4 = (n % 10);
	return d2 * 1000 + d3 * 100 + d4 * 10 + d1;
}
inline int calc_R(register int n) {
	register int d1 = n / 1000;
	register int d2 = (n % 1000) / 100;
	register int d3 = (n % 100) / 10;
	register int d4 = (n % 10);
	return d4 * 1000 + d1 * 100 + d2 * 10 + d3;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int T;
	cin >> T;
	for (register int t = 0, A, B, D, S, L, R; t < T; ++t) {
		bool visit[10000]{ false };
		string dp[10000]{ "" };
		cin >> A >> B;
		queue<int> q;
		q.push(A);
		visit[A] = true;
		while (!q.empty()) {
			auto a = q.front(); q.pop();
			if (a == B)
				break;
			if (!visit[D = calc_D(a)])
				visit[D] = true, dp[D] = dp[a] + "D", q.push(D);
			if (!visit[S = calc_S(a)])
				visit[S] = true, dp[S] = dp[a] + "S", q.push(S);
			if (!visit[L = calc_L(a)])
				visit[L] = true, dp[L] = dp[a] + "L", q.push(L);
			if (!visit[R = calc_R(a)])
				visit[R] = true, dp[R] = dp[a] + "R", q.push(R);
		}
		cout << dp[B] << "\n";
	}
	return 0;
}
// *&)*@*

1. S의 조건에서 실수가 있어서 정답을 도출하기 힘들었습니다. n -= 1 이후 n이 0일때 9999로 변경이 아니라 입력받은 그 자체가 0일때 9999로 변경입니다.
2. 그 외에는 일반적인 dp 형태로 진행합니다.