![[레벨:1]](http://algospot.com/zbxe/modules/point/icons/default/1.gif "포인트:330point (88%), 레벨:1/30"){kind=icon}
룡이162번 실험데이터 복구하기 삽질하다가 도움을 요청합니다 !!
주어진 스트링의 조합으로 구하고 있는데요..
아무리 생각해도 스트링을 합치는 순서에 따라 영향이 있어서
모든 순서를 체크하도록 했더니 최대 15!.... TLE 가 나버리네요.
문제랭크 리스트를 보면 0ms 가 있는 걸로 봐서 모든 조합의 수를 확인할 필요가 없는거 같은데요 !
긴 거부터 합쳐볼까... 짧은 거부터 해볼까.. 사전순 앞에거부터 해볼까..
경우의 수를 줄이려고 별 짓을 다 해봤는데 모두 실패해서요 ㅜ
불쌍한 코더 하나 편하게 잘 수 있도록 힌트 좀 주실 수 없을까요 ? - ㅁ-;;
![[레벨:6]](http://algospot.com/zbxe/modules/point/icons/default/6.gif "포인트:3330point (7%), 레벨:6/30"){kind=icon}
리베
이 문제는 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번 문제 해설