twicedtna   3년 전

사실 국어이슈로 틀렸었는데 이거 찾고 진실을 깨달았습니다

blender333   3년 전

글 읽고 풀어봤는데 2번을 실행할 수 있는 상황에서 무조건 1대신 2를 실행하도록 짜서 맞았습니다

그리디 알고리즘문제라서 이게 맞는거같긴한데다혹시 2번을 할 수 있는 상황임에도 1번을 하는게 결과적으론 더 적은 횟수로 0을 만들 수 있는 상황이 없다는 것을 증명하고 푸셨나요? 반례가 없다는걸 증명하는 방법을 모르겠어서 질문한번 드립니다

twicedtna   3년 전

슬프게도 저는 알고리즘 전문가가 아니라서 제가 생각한 풀이가 맞는지 증명하고 풀지는 않았어요.

그리디 알고리즘의 증명법 중에 "Greedy stays ahead"나 "Exchange argument"를 쓰면 되지 않을까 싶지만 실제 증명까지는 모르겠네요ㅠㅠ

blender333   3년 전

ㅇㅎ넵 나중에 한번 공부해봐야겠네요..

chlghksdyd24   3년 전

좋은 반례 감사합니다.

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