shfshfdl   2년 전

알고리즘을 생각은 했는데 최적해가 보장됨을 생각하지 못하겠어요.. 도움부탁드려요

우선 탐욕적으로 지금 선택하는 값과 이전의 값이 가장 작은것을 계속 memoization 하면서

답을 도출하면 될것 같다는 생각을 했습니다.


그런데 이게 정답을 도출하게 되는지 어떻게 판별해야할지 모르겠습니다.

이전단계에 큰값을 골라야 최적해가 되는 경우도 있을 것도 같은데


그런 경우가 없는지 어떻게 판별하는지 최적해 증명에 대해서

의견 주실 분이나 참고 자료 알려주시면 감사하겠습니다.


많은 도움 부탁드리겠습니다.

sgchoi5   2년 전

기존 질문을 한 번 체크해 보심이..

shfshfdl   2년 전

네~답 감사합니다~

이문제뿐만 아니라 먼가 dp에 대한 확신을 얻는 받법이나 증명 쪽이 궁금해서 글썻었습니다~ㅎ

감사합니다

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