스시가 무한대로 제공되니, 답이 되려면 될수 있는 한 가성비가 좋은 스시부터 먹어야 함은 자명하죠. 그렇다고 그리디로 풀면 다 쓰지 못하고 예산이 남는 케이스가 생기니 답이 안 나옵니다.
저는 적당히 threshold를 두고 예산이 이보다 크면 가성비가 가장 좋은 스시부터 먹은 후에 남은 금액에 대해서 dp를 적용했습니다. 이걸로도 답은 나오지만 다른 분들은 좀 더 똑똑하게 푸신 것 같네요. 요는 최대한 가성비가 좋은 스시부터 먹되 예산을 남기지 않는 겁니다.
bluefa
회전초밥 문제를 푸신분들의 솔루션을 보니까
dp 와 그리디 알고리즘을 섞어서 쓴 솔루션이 존재하던데,
이런 문제를 knap sack(?) 이라하는데 제가 알기로는 그리디 알고리즘으로는
해결하지 못 하는 걸로 알고 있었는데, 제가 지금까지
잘 못 알고있었나 해서 질문드립니다.
knap sack 문제를 그리디 알고리즘으로 해결할 수 있나요?
8년 전