162번 실험데이터 복구하기

  • 룡이
    룡이

    162번 실험데이터 복구하기 삽질하다가 도움을 요청합니다 !!
    주어진 스트링의 조합으로 구하고 있는데요..아무리 생각해도 스트링을 합치는 순서에 따라 영향이 있어서모든 순서를 체크하도록 했더니 최대 15!.... TLE 가 나버리네요.
    문제랭크 리스트를 보면 0ms 가 있는 걸로 봐서 모든 조합의 수를 확인할 필요가 없는거 같은데요 !긴 거부터 합쳐볼까... 짧은 거부터 해볼까.. 사전순 앞에거부터 해볼까..경우의 수를 줄이려고 별 짓을 다 해봤는데 모두 실패해서요 ㅜ
    불쌍한 코더 하나 편하게 잘 수 있도록 힌트 좀 주실 수 없을까요 ? - ㅁ-;;

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]


    14년 전
3개의 댓글이 있습니다.
  • hyunhwan
    hyunhwan

    이 문제는 TSP 문제랑 같은 문제라고 볼 수 있습니다.
    일단 brute force한 접근을 하실 경우에는 말씀하신데로 따지게 되는 경우의수가 15! 이니까 제 시간에 나오지 않겠죠?
    참고로 TSP 문제의 경우 시간 복잡도 O(n^2 * 2^n)의 dynamic programming 솔루션이 존재합니다. 이 방법을 이용하시면 Accepted를 받으실 수 있을겁니다. 아래의 링크들을 참고하시길 바랍니다.
    http://deliadeea.blogspot.com/2007/06/tsp-dynamic-programming.html
    http://algospot.com/zbxe/?mid=editorial&search_target=title_content&search_keyword=TSP&document_srl=48343 여기서 D번 문제 해설


    14년 전 link
  • 룡이
    룡이

    자세한 답변 감사합니다~
    SRM 456 에서도 양초 쪼개기에 바이너리 서치를 적용하고..
    이것도 예쁘게 설명되어 있는 문제들에 적용가능한 알고리즘을 떠올린다는게 쉽지 않네요..
    TSP 알고리즘으로 열심히 해보고 있는데 잘 되지는 않네요 ㅜ_ㅜ
    Edge 간의 비용이 첫 단계에서 적용이 안되고 중간마다 체크해줘서 시간이 오래 걸리는거 같아요.
    0ms 답안은 대체 어떤 알고리즘일지 궁금해지네요.
    꼭 풀어서 확인해 봐야겠어요 ㅜ


    14년 전 link
  • 룡이
    룡이

    흑.. 드디어 풀었습니다 ㅜ (집에 가야지 ;;)
    Cost 를 초기에 정의할 수 있군요 - ㅁ-;;
    감사합니다 !!
    TSP 알고리즘 하나 고이 구현해 놓아야겠네요 ㅋ


    14년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.