BOJ 6051 - 시간 여행

BOJ 6051 - 시간 여행

특이한 문제인데, 굳이 따지자면 Persistent Stack이라고 볼 수 있다.

지금은 테스트 데이터가 빈약해 그냥 브루트포스로 풀리는 모양이다.

각 자료가 <자신이 갖고 있는 값, 자신의 이전 곳> 을 가진다고 해보자.

과거로 돌아가도 자신의 이전 곳을 알고있다면 그 때부터 스택을 다시 쌓아갈 수 있으므로 문제없다.

이렇게 풀면 시간복잡도가 $O(N)$이다.

이게 골드 3치곤 꽤나 생각하기 어려운 문제인데, 데이터가 어서 추가되어야 할 것 같다.

void solve() {  
   int n, k;  
   cin >> n;  
   vector<pi> Q(n + 5);  
   // 자신이 갖고 있는 값, 자신의 이전 곳  
   vector<pi> x(n + 1, mp(-1, 0));  
   for (int i = 1, j = 0; i <= n; i++) {  
      string cmd;  
      cin >> cmd;  
      if (cmd == "a") {  
         cin >> k;  
         x[i] = {k, j};  
         j = i;  
      } else if (cmd == "s") {  
         x[i] = {x[j].fi, j};  
         j = x[j].se;  
      } else {  
         x[i] = {x[j].fi, j};  
         cin >> k;  
         j = x[k].se;  
      }  
      cout << x[j].fi << endl;  
   }  
}