글 읽기 - (1450: 냅색문제) Python 질문

wch18735 2년 전 0

Meet in the middle 알고리즘을 이용해 문제를 풀려고 시도했습니다.

코드를 설명드리면

ceil 을 이용해서 원소가 하나일 때, list_A에 원소가 모이도록 했습니다.
이분탐색 과정에서 부분집합의 합 값들끼리 더했을 때, C보다 작은 것들의 개수를 세도록 했습니다.

혹시 논리상 틀린 곳이 있거나, 반례가 있다면 댓글 부탁드립니다!!

현재까지는

<문제>

1 1

답: 2

가 나와야하는 것이 1이 나오는 것을 확인했습니다.

from itertools import combinations
from math import floor, ceil

if __name__=="__main__":
    N, C = map(int, input().split(' '))

    weights = list(map(int, input().split(' ')))

    list_A = weights[:ceil(N/2)]
    list_B = weights[ceil(N/2):]

    # 리스트 길이 (원소 개수)
    len_A = len(list_A)
    len_B = len(list_B)

    # 부분 집합 합
    subset_a = []
    subset_b = []

    for num in range(len_A + 1):
        for sub_set in combinations(list_A, num):
            subset_a.append(sum(sub_set))

    for num in range(len_B + 1):
        for sub_set in combinations(list_B, num):
            subset_b.append(sum(sub_set))

    # list_A 오름차순 정렬
    subset_a.sort(key=lambda x: x)

    # 답
    answer = 0

    # 정렬된 요소에 이분탐색 시행
    for element_b in subset_b:
        # 용량보다 큰 경우
        if element_b > C:
            continue

        # 이분 탐색
        left_idx = 0
        right_idx = len(subset_b)
        
        # 값을 만족하는 rightmost
        while left_idx < right_idx:
            mid = floor((left_idx + right_idx) / 2)
            if element_b + subset_a[mid] > C:
                right_idx = mid
            else:
                left_idx = mid + 1
        
        # right_idx -> 개수
        answer += right_idx
    
    # 총 경우의 수
    print(answer)

wch18735 2년 전 0

42번째 줄의 len(subset_b) -> len(subset_a) 바꾸어 해결했습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

(1450: 냅색문제) Python 질문

wch18735 2년 전 0

wch18735 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말