gyjinro   2년 전

아이디어는 분할해서 탐색을 한 후 결과를 정리하는 방식입니다.

아래와 같은 방시으로 풀었는데요.. 어디서 틀렸는지 감이 안 잡히네요 ㅠ

먼저 절반을 나눠서 dict 경우의 수를 완전 탐색하여 '최종 무게(C를 초과하지 않는다면): 그 무게가 등장한 수'를

왼쪽은 dic에 오른쪽은 dic2에 넣습니다.

dic을 정렬 한 후 키 값을 vals에 넣고

카운터는 acc에 누적하여 리스트를 만들었습니다.

그리고 dic2에 있는 vals에서 '최대 무게 - 무게 값'의 인덱스를 bisect_left로 찾아서,

acc에서 그 인덱스와 dic2의 해당 무게 값의 카운트를 곱한 값을 결과에 더해 갔습니다.

(vals 보다 큰 값이 인덱스 에러를 내는 건이 있어서, 크게 문제 되지 않을거라고 생각해서 acc의 마지막 값을 한번 더 append 해서 vals보다 acc가 요소를 하나 더 갖고 있습니다.)

어디서 틀린 걸까요 ㅠ_ㅠ

gyjinro   2년 전

bisect_left가 문제 였네요.. 허허

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