juhyun16   4년 전

제목 그대로 1315번 rpg 문제의 다른 풀이법이 궁금합니다. 문제 힌트/분류에서 다이나믹 프로그래밍으로 분류 되어있어서 힌트를 얻어 다이나믹으로 풀었습니다. (생각하기 어려워서 도움을 받아 풀었던 문제입니다.)

solve(int str, int intelligent) 라는 재귀함수를 만들었습니다. 현재 캐릭터가 힘을 str 만큼 가지고 있고, 지력을 intelligent 만큼 가지고 있을 때 최대로 깰 수 있는 퀘스트의 갯수를 반환하도록 정의했습니다.

재귀함수 내부에서 모든 퀘스트 목록을 다 뒤져서 최대한의 points를 얻어오고 이 포인트로 부터 (힘, 지력)을 자유분배하여 재귀호출했습니다.

아무튼 제가 궁금한 것은 다른분들의 풀이법인데, 소스를 보니 priority_queue를 선언해서 BFS 스럽게 푸신분들도 계시더라고요. priority_queue + BFS => Dijkstra ? 라고 생각하면 뭔가 최단거리 문제처럼 푸신 것도 같은데 소스를 봐도 잘 모르겠어서 질문남깁니다.


rpg 문제를 최단거리 문제로 응용해서 풀 수도 있는건가요?


smu201111192   4년 전

srm 424 Division One - Level Two 문제네요.

https://community.topcoder.com... 에디토리얼입니다.


그리고 제 생각에는 단순히 비재귀와 재귀의 차이인 같습니다.


juhyun16   4년 전

@smu201111192 답변 감사합니다. 많은 도움이 되었습니다~

댓글을 작성하려면 로그인해야 합니다.