ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 2568
    알고리즘/acmicpc 2015. 2. 25. 13:33

    초등부의 전깃줄 문제에서 한발 나아간 문제.

    기본적으로 LIS를 이용해서 풀 수 있는 것은 똑같지만 Input의 개수가 1000배이상 증가해서

    O(N*N) 기본탐색 알고리즘을 사용하면 시간초과가 날게 틀림없으므로

    좀 더 효율적인 자료구조를 활용해 속도를 높일 필요가 있었다.


    나는 priority queue를 이용해서 풀었는데

    priority queue는 이전 까지 탐색했던 line중에서 LIS값이 높은 순위로 저장되어있다.

    priority queue는 pair<int, int>로 이루어져 있는데 pq가 pair.first를 통해서 정렬한다는 점을 알면 구현하기 편리하다


    d값, value값, idx값 총 세가지 값이 필요한데 나는 pair.second로 idx값을 넣어서 value값은 넣지 않고 idx값을 통해서 참조 할 수 있게 만들었다.




    '알고리즘 > acmicpc' 카테고리의 다른 글

    9489  (0) 2015.02.26
    2517  (0) 2015.02.26
    2568  (0) 2015.02.25
    2109  (0) 2015.02.22
    1914  (0) 2015.02.22
    9463  (0) 2015.02.21

    댓글 0

Designed by Tistory.