1591: 수열 복원
2016. 3. 8. 12:23ㆍ알고리즘 문제풀기/각종 OJ 풀이
일단, 이웃한 \((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)개를 효과적으로 관리하기 위하여 나는 해싱을 사용했다.
'알고리즘 문제풀기 > 각종 OJ 풀이' 카테고리의 다른 글
AtCoder (0) | 2016.09.04 |
---|---|
나코더 방학 연습 2주차 풀이 (0) | 2016.08.07 |
나코더 방학 연습 1주차 풀이 (0) | 2016.07.28 |
[algospot] [NUMB3RS] 두니발 박사의 탈옥 (0) | 2014.05.30 |
[KOISTUDY] [017D] [381] 격자 읽기 (0) | 2014.02.25 |