[BOJ] 1591번: 수열 복원

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

일단 N-M+1개의 수열을 2개로 분리하는 아이디어까지는 생각해냈습니다. (예를 들어 3 5 1 2일 경우 3 5 1 / 5 1 2로). 그런데 저는 여기서 모든 수열을 전부 2개로 쪼개어, 일치하는 것들을 undirected edge로 연결한 후 Hamiltonian path를 찾는 문제로 생각해서 대체 이걸 어떻게 Polynomial time에 풀라는건가 하고 애를 먹었습니다. 엄청 고민하다가 coloredrabbit님의 블로그(http://coloredrabbit.tistory.com/41)의 도움을 받아 풀이를 해낼 수 있었습니다. 좋은 문제네요.

https://github.com/blisstoner/BOJ/blob/master/1591.cpp