[4] [Class 3] - 백준 9019 DSLR

www.acmicpc.net/problem/9019

9019번: DSLR

 

처음에는 rotate함수 이용해서 string을 돌려서 짰는데

그러다보니 시간 초과가 나는 것이다. 

int로 바꿔 계산하니 올바른 결과가 나왔다. 

 

#include <bits/stdc++.h>

using namespace std;

bool visited[10001];

int main(){
  ios_base :: sync_with_stdio(false); 
  cin.tie(NULL);

  int T;
  cin >> T;
  queue<pair<int, string> > q;

  while(T--){
    int A, B;

    cin >> A >> B;
    q.push(make_pair(A, ""));

    while(!q.empty()){
      pair<int, string> now = q.front();
      q.pop();
      
      int x = now.first;
      if(x == B) {
        cout << now.second << '\n';
        break;
      }
      int twice = (x * 2) % 10000;
      if(!visited[twice]) {
        visited[twice] = true;
        q.push(make_pair(twice, now.second + "D"));
      }

      int minus = (x == 0 ? 9999 : x - 1);
      if(!visited[minus]) {
        visited[minus] = true;
        q.push(make_pair(minus, now.second + "S"));
      }

      int left = (x % 1000) * 10 + (x / 1000);
      if(!visited[left]) {
        visited[left] = true;
        q.push(make_pair(left, now.second + "L"));
      }
      
      int right = (x % 10) * 1000 + (x / 10);
      if(!visited[right]) {
        visited[right] = true;
        q.push(make_pair(right, now.second + "R"));
      }
    }

    while(!q.empty()) {
      pair<int,string> now = q.front();
      
      q.pop();
    };

    memset(visited, false, sizeof(visited));
  }

  return 0;
}