[백준] 1450번 냅색문제 - 파이썬(Python)

문제 (링크)

https://www.acmicpc.net/problem/1450

1450번: 냅색문제

 

나의 풀이

import sys
from itertools import combinations

input = sys.stdin.readline

n, c = map(int, input().split())
arr = list(map(int, input().split()))

# meet in the middle
arr_1 = arr[:n//2]
arr_2 = arr[n//2:]

subsum_a = []
subsum_b = []

for i in range(len(arr_1) + 1):
    comb_a = combinations(arr_1, i)

    for comb in comb_a:
        subsum_a.append(sum(comb))
        
for i in range(len(arr_2) + 1):
    comb_b = combinations(arr_2, i)
    
    for comb in comb_b:
        subsum_b.append(sum(comb))

subsum_a.sort()
ans = 0

# subsum_a와 subsum_b의 값을 더하는 작업을 이분탐색으로 진행
for element_b in subsum_b:
   
   # 이미 subsum_b의 값이 c를 넘었다면 작업 X
    if element_b > c:
       continue
    
    start = 0
    end = len(subsum_a) - 1

    while start <= end:
        mid = (start + end) // 2

        if subsum_a[mid] + element_b > c:
            end = mid - 1
        
        else:
            start = mid + 1
    
    ans += end + 1

print(ans)

코드 설명 및 풀이법

이전에 풀었던 부분수열의 합 문제와 사실상 로직이 동일하다.

https://seongonion.tistory.com/102

[백준] 1208번 부분수열의 합 2 - 파이썬(Python)

입력으로 받은 배열을 반으로 나누어 각각의 부분집합의 합을 구해준 후, 이분탐색을 통해 두 배열의 부분집합의 합을 더하여 c이하의 값을 찾아주면 된다.

 

테스트케이스에서도 확인할 수 있듯, 배낭에 아무것도 넣지 않는 경우 또한 존재하기 때문에 해당 부분을 예외처리할 필요 없이 그냥 itertools.combinations함수를 사용하면 된다.

 

이분탐색에서 개수를 세어주는 방식이 조금 독특했는데, 이분탐색을 완료한 이후 최종적으로 기록된 end값을 기준으로 개수를 세어주는 것이다.

 

subsum_a는 정렬되어 있고, 이분탐색을 진행할수록 subsum_a의 원소와 subsum_b의 원소를 더한 값이 c이하인 right_most값에 가까워진다.

 

최종적으로는, right_most값의 인덱스 값이 end에 기록되게 되고, 개수를 세주어야하기 때문에 end에 1을 더한 값을 ans에 더해주면 개수를 구할 수 있다 (인덱스는 0부터 시작하니까).