PY-L4-034 / 탐색 최적화
만남의 중간 부분합
고급문제
숫자 리스트 values에서 합이 target인 부분집합이 있는지 불리언으로 반환하세요. 음수를 허용하며 빈 부분집합의 합은 0입니다. 길이는 30 이하입니다.
solve(*args) 함수에서 값을 반환하세요. print 출력은 정답 판정에 사용하지 않습니다.
입출력 예시
예제 1
입력: [[3,-2,7],5] 반환: true
예제 2
입력: [[2,4],3] 반환: false
힌트
배열을 둘로 나누고 각 부분합을 결합하세요.
해설·정답 보기
Meet-in-the-middle로 두 절반의 부분합을 만듭니다. 음수가 있어서 단순한 양수 가지치기는 사용할 수 없습니다.
def solve(values, target):
def sums(items):
result = [0]
for value in items:
result += [s + value for s in result]
return result
mid = len(values) // 2
right = set(sums(values[mid:]))
return any(target - s in right for s in sums(values[:mid]))solution.py결과 비교
코드는 이 브라우저에 자동 저장돼요.
풀이 결과
코드를 작성하고 채점하기를 눌러보세요.
학습용으로 제공된 조건을 확인해요. 알고리즘 사용 방식·설계 의도는 해설과 함께 비교해보세요.