🚀 문제
https://www.acmicpc.net/problem/1450
🚀 정답 코드
import sys
from itertools import combinations
input = sys.stdin.readline
# 입력 받기: 물건 수 N, 최대 무게 C
N, C = map(int, input().split())
items = list(map(int, input().split()))
# 아이템 리스트를 절반으로 나눌 기준 인덱스
mid = N // 2
arr1 = []
# 첫 번째 절반 (왼쪽)의 모든 부분집합의 합 구하기
for i in range(0, mid + 1):
combi = combinations(items[:mid], i) # i개를 고르는 조합 생성
for c in combi:
sum_c = sum(c) # 조합의 합 계산
if sum_c <= C: # 조건 만족 시에만 추가
arr1.append(sum_c)
arr2 = []
# 두 번째 절반 (오른쪽)의 모든 부분집합의 합 구하기
for i in range(0, N - mid + 1):
combi = combinations(items[mid:], i) # i개를 고르는 조합 생성
for c in combi:
sum_c = sum(c) # 조합의 합 계산
if sum_c <= C: # 조건 만족 시에만 추가
arr2.append(sum_c)
# 이분 탐색을 위해 정렬
arr2.sort()
total = 0
# arr1의 각 합에 대해, arr2에서 조건을 만족하는 쌍의 개수를 이분 탐색으로 찾기
for a1 in arr1:
left = 0
right = len(arr2) - 1
# arr2에서 a1 + b <= C 를 만족하는 b의 개수를 찾기
while left <= right:
mid = (right - left) // 2 + left
if arr2[mid] <= C - a1:
# 조건 만족 → 더 큰 b가 있을 수도 있으니 오른쪽으로 이동
left = mid + 1
else:
# 조건 초과 → 오른쪽을 줄여야 함
right = mid - 1
# left는 C - a1 이하인 b의 개수
total += left
# 최종 조건을 만족하는 조합의 개수 출력
print(total)🚀 시행착오 했던 부분
시간 복잡도를 개선할 아이디어가 부족했다.
현재 가방 들어간 물건들의 현황을 알고 있어야하고, 현재 물건을 넣은 경우, 넣지 않은 경우로 분리해서 그 다음 케이스를 고려해야하기 때문에 결국 모든 케이스를 고려하는 것이 가장 간단한 방법이라고 생각했다.
하지만 모든 케이스를 핸들링 하려면 2^30의 케이스를 모두 고려해야하기 때문에 시간 복잡도를 개선해야할 필요는 있다고 생각했지만 방법을 생각하지 못했다.
생각보다 해결 방법은 간단했던 것 같다.
가방에 넣을 물건을 두 배열로 분리하고 두 배열의 모든 경우의 수를 구하면 2^15 정도로 시간 복잡도가 간소화된다.
이후 왼쪽 배열에서 하나의 조합당 오른쪽 배열에서 가능한 조합의 수를 이진 탐색으로 처리하면 문제를 해결할 수 있다.
나도 잘하고 싶다..!