[백준/C++] DSLR

 

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 이전에 풀었던 문제들과 큰 차이가 없는 문제다.

가장 적은 연산으로 특정 수를 만드는 것을 목표로 하기 때문에 BFS로 풀 수 있다.

 

BFS로 구할 경우 어떤 수 A를 DSLR 연산으로 다른 수 k를 만들 수 있고 이 때, k가 처음 나온다면, k가 나오는 가장 빠른 방법이 되기 때문이다.

 

그러므로 배열을 이용해 어떤 수A를 연산해  k를 처음 만들었을 경우에 어떤 연산으로 k가 되었는지를 array[k]에 저장한다.

그리고 A에서 k로 변했다고 저장하기 위해 arrayIdx[k]에 A를 저장한다.

 

(어떤 수에서 변했는지 저장하는 이유는 *2 연산으로 2가 나올 경우 5001, 1처럼 두가지가 가능한 경우가 있어서 역 연산 대신 수를 저장하는 것이다.)

 

 

​

[아이디어 정리]

1. 어떤 수에서 변했는지 저장할 배열과, 어떤 연산으로 변했는지 저장할 배열을 만든다.
2. 이후 BFS로 연산을 통해 A를 K라는 수로 변환하고 만약 K라는 수를 처음 만들었다면, K는 A에서 어떤 연산으로 만들었다는 정보를 배열에 저장한다.
3. 목표로 했던 B라는 수를 만들면 배열의 정보를 이용해 어떤 연산으로 B를 만들었는지 출력한다.

 

 

Code

 

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
using namespace std;
char V[10001];
int mV[10001];
int ChangeNum(int n, char c)
{
	int tmp;
	if (c == 'D')
	{
		n *= 2;
		n %= 10000;
	}
	else if (c == 'S')
	{
		n += 9999;
		n %= 10000;
	}
	else if (c=='L'){
		tmp = n / 1000;
		n *= 10;
		n += tmp;
		n %= 10000;
	}
	else if (c=='R')
	{
		tmp = n % 10;
		n /= 10;
		n += tmp*1000;
		n %= 10000;
	}
	return n;
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	int tc;
	cin >> tc;
	int a, b;
	for (int t = 0; t < tc; t++)
	{
		cin >> a >> b;
		for (int i = 0; i < 10001; i++) {
			mV[i]=10001;
		}
		mV[a] = -1;
		queue<int> q;
		q.push(a);
		int nNum, nxt;
		while(!q.empty())
		{
			nNum = q.front();
			q.pop();
			if (nNum == b) {
				break;
			}
			nxt = ChangeNum(nNum, 'D');
			if (mV[nxt] >10000) {
				V[nxt] = 'D';
				mV[nxt] = nNum;
				q.push(nxt);
			}
			nxt = ChangeNum(nNum, 'S');
			if (mV[nxt] > 10000) {
				V[nxt] = 'S';
				mV[nxt] = nNum;
				q.push(nxt);
			}
			nxt = ChangeNum(nNum, 'L');
			if (mV[nxt] > 10000) {
				V[nxt] = 'L';
				mV[nxt] = nNum;
				q.push(nxt);
			}
			nxt = ChangeNum(nNum, 'R');
			if (mV[nxt] > 10000) {
				V[nxt] = 'R';
				mV[nxt] = nNum;
				q.push(nxt);
			}
		}
		string str = "";
		while(true)
		{
			if (mV[nNum] == -1) {
				break;
			}
			str = V[nNum]+str;
			int ttt = nNum;
			nNum=mV[nNum];
		}
		cout <<str<< "\n";
	}
	return 0;
}

 

---

 

처음에 *2 연산으로 수를 만드는 경우에 (5001, 1) 과 같은 예외가 존재하는 것을 생각하지 않고 역연산으로 구현했다가 틀렸다...

눈치 못챘으면 계속 억울했을뻔;;

 

 

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