부분수열의 합

문제

전 포스팅의 부분수열의 합과는 다른 문제입니다. 부분 수열의 모든합을 구하고 해당 부분수열의 합으로 나타낼수없는 최소 자연수를 구하는 문제입니다.

풀이

첫번째 방법은 집합을 늘려가는 방법입니다.
초기 집합에 0을 넣고 수열이 주어졌을때 수열의 원소들을 하나씩 꺼내면서 집합의 원소에 더한 집합을 생성하고 본래의 집합과 합칩니다. 이 과정을 끝까지 반복하면 모든 부분집합에 대한 합이 있는 집합이 생성됩니다.
예를 들면, 5,1,2 수열이 주어졌을때
{0}
{0, 5} --> 5를 전채집합에 더한뒤 합집합으로 만든다.
{0, 1, 5, 6} --> 1을 전채집합에 더한뒤 합집합으로 만든다.
{0, 1, 2, 5, 6, 7, 8} --> 2를 전채집합에 더한뒤 합집합으로 만든다.
결과로 나온 집합에 대해서 최소 자연수를 계산하면 됩니다.

두번째 방법은 비트마스킹을 이용하는것입니다.
N=3 인경우 전채 경우의 수는 2^3이며 이를 기준으로 0<=N<(1<<3)을 범위로 한다면 0 , 1, 10, 11, 100, 101, 110, 111의 이진수를 가지게 되며 이는 0을 원소의 미존재, 1을 원소의 존재라고 생각하면 모든 경우의 수를 따질 수 있습니다.

세번째 방법은 정확한 이해는 하지못했다. 추후 이해를 하게 되면 포스팅을 수정하겠습니다.

코드

'''
Created by jun on 21/05/20
'''
#집합을 늘려가는 방법
N = int(input())
S = list(map(int,input().split()))
part_sum = {0}
for x in S:
    part_sum |= {y+x for y in part_sum}
for res in range(100000*20+1):
    if res not in part_sum:
        print(res)
        break

'''
Created by jun on 21/05/20
'''
#비트마스킹
N = int(input())
S = list(map(int, input().split()))
num_set = set(range(1,20*100000+1))
for i in range(1<<N):
    part_sum = 0
    for j in range(N):
        if i & 1 << j:
            part_sum += S[j]
    num_set.discard(part_sum)
print(min(num_set))

'''
'''
n=int(input())
a=sorted(map(int,input().split()))
s=0
for x in a:
  if s+1<x:
    print(s+1)
    exit()
  s+=x
print(s+1)

새로 알게된 사실

집합을 늘려가면서 모든 부분집합의 합을 구하는법
비트마스킹으로 전체 경우의수를 따지는법

참조

https://www.acmicpc.net/source/17060132
https://www.acmicpc.net/source/29513992
https://www.acmicpc.net/source/21876449