dp 문제에서 pre[] 배열을 선언해서 뒤로 추적해 나갈때 deque의 활용

14002번 문제 풀이의 맨 마지막을 보면 

deque를 활용하여서 push_front(a[cur]);을 시행하는데,

이걸 그냥 그대로 deque가 아니라 vector로 바꿔서 답을 출력해보면, 

 

10 20 30 50 으로 출력되어야 할 값이, 

50 30 20 10 으로 출력된다. 

이 형태에서 내가 vector를 떠올렸을때 해결할 수 있는 방법은, vector 내부의 원소들의 순서를 뒤집어 주는 것이고, 

그걸 하기 위해 찾아보니 

algorithm헤더에 reverse 함수가 정의되어 있어서 그걸 사용하면 되었다. 

 

reverse(v.begin(),v.end())형태로 활용하면 되고, 그렇게 reverse를 해주고 나서 벡터 원소들을 출력해보면

원하는 값인 10 20 30 50이 나오는걸 확인할 수 있었다. 

하지만 deque로 값을 push_front로 받아서 다시 출력해주면 front로 나오는 순서대로 10 20 30 50 이 나오게 되니까

reverse 함수를 사용하지 않아도 되고, 애초부터 deque로 하는것이 훨씬 깔끔한 방법이 될것이다.

그러니 이번 문제를 통해서 어떤 형태로 값을 담는지, 그리고 어떤 순서로 출력되어야 하는지에 대해서  생각해보면서 

애초에 vector를 사용할지, 혹은 deque를 사용할지 결정해서 선택하는게 좋을것 같다.

 이번 문제를 통해서 익숙해져보도록 하자.