728x90
문제 (링크)
https://www.acmicpc.net/problem/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
입력으로 받은 배열을 반으로 나누어 각각의 부분집합의 합을 구해준 후, 이분탐색을 통해 두 배열의 부분집합의 합을 더하여 c이하의 값을 찾아주면 된다.
테스트케이스에서도 확인할 수 있듯, 배낭에 아무것도 넣지 않는 경우 또한 존재하기 때문에 해당 부분을 예외처리할 필요 없이 그냥 itertools.combinations함수를 사용하면 된다.
이분탐색에서 개수를 세어주는 방식이 조금 독특했는데, 이분탐색을 완료한 이후 최종적으로 기록된 end값을 기준으로 개수를 세어주는 것이다.
subsum_a는 정렬되어 있고, 이분탐색을 진행할수록 subsum_a의 원소와 subsum_b의 원소를 더한 값이 c이하인 right_most값에 가까워진다.
최종적으로는, right_most값의 인덱스 값이 end에 기록되게 되고, 개수를 세주어야하기 때문에 end에 1을 더한 값을 ans에 더해주면 개수를 구할 수 있다 (인덱스는 0부터 시작하니까).
'알고리즘 > 문제풀이' 카테고리의 다른 글
[백준] 2206번 벽 부수고 이동하기 - 파이썬(Python) (0) | 2021.10.03 |
---|---|
[백준] 14503번 로봇청소기 - 파이썬(Python) (0) | 2021.10.03 |
[백준] 14502번 연구소 - 파이썬(Python) (0) | 2021.10.01 |
[백준] 9663번 N-Queen - 파이썬(Python) (13) | 2021.09.30 |
[백준] 1208번 부분수열의 합 2 - 파이썬(Python) (0) | 2021.09.30 |