1106번 - 호텔
1202 - 보석 도둑 문제처럼 그리디하게 투자한 돈 대비 고객이 가장 많은 도시부터 투자하고, 남는거를 다른 도시에서 빼도 되지 않나요...?
분명 이렇게 풀 수 있을 것 같아 질문 남깁니다.
나이브한 그리디로는 잘 되지 않을 것 같습니다.
첨부한 입력에서 어떻게 두 케이스를 구별해야 좋을까요?
@lcr7324
네 입력 잘 봤습니다. 그런데 첨부하신 입력에서돈 : 고객 수로 나와야 하는데
고객 수 : 돈 으로 나온 것 같아 질문 드립니다.
아 그러네요, 뒤집어서 넣었군요. 입력을 정정하겠습니다.
요지는 비율이 동일해도 상황에 따라 선택하게 되는 도시가 달라질 수 있고, 그리디한 전략으로 도시를 priority queue에 넣고 바꿔끼우는 방식의 풀이가 어려워보인다는 뜻이었습니다.
댓글을 작성하려면 로그인해야 합니다.
factories 1년 전
1202 - 보석 도둑 문제처럼 그리디하게 투자한 돈 대비 고객이 가장 많은 도시부터 투자하고, 남는거를 다른 도시에서 빼도 되지 않나요...?
분명 이렇게 풀 수 있을 것 같아 질문 남깁니다.