1591: 수열 복원
문제 링크일단, 이웃한 \((M+1)\)개의 숫자들에 대해서, 앞의 \(M\)개와 뒤의 \(M\)개는 \((M-1)\)개가 겹친다. 그렇다면, \((N-M+1)\)개의 수열에서, 한 수열에서 \((M-1)\)개가 겹치는 다른 수열로 옮겨간다고 생각할 수 있다. 그런데 \((N-M+1)\)개를 정점으로 잡으면 Hamiltonian Path를 구해야 하기 때문에 복잡하다. 따라서, \((M-1)\)개를 정점으로 잡고, 각각의 \((N-M+1)\)개의 수열을 간선으로 만들면 Euler Tour를 구하면 된다. (M-1)개를 효과적으로 관리하기 위하여 나는 해싱을 사용했다.
2016. 3. 8. 12:23