[c++]백준 9019 - DSLR (DP)

0. [c++] 백준

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

1. 풀이

2. 소스코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
 
using namespace std;
 
 
int N, object;
 
void dp(const int a) {
    queue<int> qu;
    vector<bool> visited(10001, false);
    vector<string> ans(10001);
 
    visited[a] = true;
    qu.push(a);
    
    while (!qu.empty()) {
        int here = qu.front();
        qu.pop();
        
        int D = here * 2;
        D %= 10000;
 
        int S = here - 1;
        if (here == 0)
            S = 9999;
        int L = here * 10;
        L += (here / 1000);
        L -= (here / 1000) * 10000;
 
        int R = here / 10;
        R += (here % 10) * 1000;
 
        //cout << D << " " << S << " " << L << " " << R << endl;
 
        if (!visited[D]) {
            qu.push(D);
            visited[D] = true;
            ans[D] = ans[here] + "D";
        }
 
        // S 연산
        if (!visited[S]) {
            qu.push(S);
            visited[S] = true;
            ans[S] = ans[here] + "S";
        }
 
        // L 연산
        if (!visited[L]) {
            qu.push(L);
            visited[L] = true;
            ans[L] = ans[here] + "L";
        }
 
        // R 연산
        if (!visited[R]) {
            qu.push(R);
            visited[R] = true;
            ans[R] = ans[here] + "R";
        }
 
        if (visited[object])
            break;
    }
    cout << ans[object] << endl;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> N;
 
    while (N--) {
        int a;
        cin >> a >> object;
        
        dp(a);
    }
 
}

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!