https://www.acmicpc.net/problem/1480 와 미친.. dp 왜이렇게 재밌는지 모르겠다 이 문제는 배낭 문제+비트마스크다. 가장 큰 문제는 가방이 여러개라는거다. 처음에는 가방 1에서 모을수있는만큼 최대한 보석을 모으고 그 목록을 따로 저장 후 다음 가방으로. 이런식이었는데 이렇게 하면 안된다. 각각의 최댓값이 전체 문제의 최댓값이 안 될수도 있기 때문이다. 따라서 모든 경우의 수를 조합해야된다. 보석 수나 가방 용량 등을 봤을때 수가 적어서 모든 수를 조합하고 적당히 메모이제이션 하면 잘 나올거라고 예측 가능하다. # -*- encoding: cp949 -*- import sys sys.setrecursionlimit(1000000) def getmax(m, capacity, j..