코딩 테스트를 위한 소프티어(Softeer) 연습 문제 중 금고털이 문제를 풀어보았다. 연습 문제 - 금고털이 난이도 : level 2 정답률 : 33% https://softeer.ai/practice/info.do?idx=1&eid=395 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 문제 해설 금고에 금속이 있다. 이 금속들을 배낭에 담는 문제이다. 배낭은 담을 수 있는 무게가 정해져 있고 각 금속들은 무게와 무게당 가격이 정해져 있다. 이때 배낭에 가능한 비싸게 배낭을 채우는 문제이다. 톱이 있어서 금속을 자를 수도 있다. 일단 N은 10^6 이므로 최소한 O(N^2) 보다는 적은 시간복잡도를 가지도록 구현해야 한다. 톱이 있다고 해서 경우의 수가 굉장히 많아..