[백준][투포인터] 냅색문제

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

1450번: 냅색문제

 

내가 작성한 코드

import sys
from bisect import bisect_right
from itertools import combinations

read = sys.stdin.readline

def read_data():
    N, C = map(int, read().rstrip().split())
    stuffs = list(map(int, read().rstrip().split()))
    return N, C, stuffs


def meet_in_the_middle(N, C, stuffs):
    def get_middle_sum(a, b):
        stuff_half = stuffs[a:b]
        sum_half = []
        for r in range(1, len(stuff_half)+1):
            for comb in combinations(stuff_half, r):
                sum_half.append(sum(comb))
        return sorted(sum_half)

    middle = N // 2
    sum_front = get_middle_sum(0, middle)
    sum_rear = get_middle_sum(middle, N)

    cnt = 1 + bisect_right(sum_front, C) + bisect_right(sum_rear, C)
    for rear in sum_rear:
        cnt += bisect_right(sum_front, C-rear)

    return cnt

N, C, stuffs = read_data()
# N, C, stuffs = 1, 1, [1]
print(meet_in_the_middle(N, C, stuffs))

• 중간에서 만나기(Meet in the middle)
  
  • 절반을 나누어 모든 합을 각각 구함 map(sum, combinations(절반, 1~len(절반)+1)
  • 각각에 대해 C이하인 개수를 구함 (bisect_right : upper bound의 index가 C이하의 개수)
  • 절반끼리의 합이 C이하인 개수를 구함

 

다른 사람이 작성한 코드

None

• 아래 블로그의 이론을 보고 작성

https://blog.naver.com/kks227/221382873753

밋 인 더 미들(Meet in the Middle) (수정: 2018-10-25)

https://blog.naver.com/chogahui05/221374387858

meet in the middle 알고리즘 - 반으로 쪼갠다.

기억해야할 것

 

• 중간에서 만나기(Meet in the middle)
  
  • exponential하게 증가하는 알고리즘에서 사용
  • 주어진 데이터의 절반씩 따로 돌림
    - (2^30) -> (2^15 + 2^15)
    - 1,073,741,824 -> 65,536
  • [예제] 합이 k이하가 되는 모든 케이스
  • [예제] 모든 케이스(조합)를 구하는 크기가 너무 클 때