factories   1년 전

1202 - 보석 도둑 문제처럼 그리디하게 투자한 돈 대비 고객이 가장 많은 도시부터 투자하고, 남는거를 다른 도시에서 빼도 되지 않나요...?

분명 이렇게 풀 수 있을 것 같아 질문 남깁니다.

lcr7324   1년 전

나이브한 그리디로는 잘 되지 않을 것 같습니다.

첨부한 입력에서 어떻게 두 케이스를 구별해야 좋을까요?

factories   1년 전

@lcr7324

네 입력 잘 봤습니다. 그런데 첨부하신 입력에서
돈 : 고객 수
로 나와야 하는데

고객 수 : 돈 으로 나온 것 같아 질문 드립니다.

lcr7324   1년 전

아 그러네요, 뒤집어서 넣었군요. 입력을 정정하겠습니다.

요지는 비율이 동일해도 상황에 따라 선택하게 되는 도시가 달라질 수 있고, 그리디한 전략으로 도시를 priority queue에 넣고 바꿔끼우는 방식의 풀이가 어려워보인다는 뜻이었습니다.

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