문제

참고1
참고2

문제

세준이는 N개의 물건을 가지고 있고, 최대 C만큼의 무게를 넣을 수 있는 가방을 하나 가지고 있다.

N개의 물건을 가방에 넣는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 $10^9$보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 $10^9$보다 작거나 같은 자연수이다.

출력

첫째 줄에 가방에 넣는 방법의 수를 출력한다.

풀이

기존 냅색 문제처럼 풀고 경우의 수를 전부 추적하는 방식을 생각했으나, 문제의 취지에 맞을 것 같지도 않고 오래 걸릴 것 같았다. C도 $10^9$여서 다른 방법을 이용해야 된다...

결국 못참고 찾아봤는데, MITM(Meet in the Middle)이라는 전략을 이용하여 풀이하는 문제였다.

리스트를 반으로 나눈 뒤, 각각의 리스트들의 수열을 만들고, 이분 탐색을 활용하는 것이다.
재귀적으로 가르지도 않고 한 번만 가르길래 띠용했었는데 문제 풀이를 통해 로직을 이해했다.

리스트1의 임의의 요소를 골라 C에서 뺀 값을 리스트2에서 찾는다. 이때 인덱스 번호는 리스트2에서 C 이하가 되는 경계점과 같다.
이런식으로 모든 요소에 접근하여 더하면 모든 경우의 수를 탐색할 수 있다.

def dfs(lst, sum, target, end_p):
    if target != end_p:
        lst.append(sum + weights[target])
        dfs(lst, sum + weights[target], target + 1, end_p)
        dfs(lst, sum, target + 1, end_p)

수열을 만드는 함수이다.
itertools의 combinations를 쓸 수도 있지만 dfs를 이용하였다.
lst의 주소를 참조하기 때문에 바로 추가해준다... 개발 에서 좋은 함수인지는 몰?루

from bisect import bisect_right
def solve():
    cnt = 0
    for i in weights1:
        cnt += bisect_right(weights2, C-i)
    return cnt

bisect 모듈의 bisect_right 함수를 이용해 이분탐색한다. 중복 값이 존재 시 left를 이용하면 다른 값이 나올 수 있다.