Python 14225번 부분수열의 합

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

14225번: 부분수열의 합

 

처음엔 이 문제를 아래처럼 재귀 방식을 이용해서 문제를 풀려고 했지만 시간 초과 에러가 떠서 다른 방법을 구글링 해봤더니

비트마스크를 이용하는 방식을 찾았다.

import sys
cnt=[]
input=sys.stdin.readline
num = [0]*2000000
n = int(input())
ary = list(map(int,input().split()))

def recur(visited,cnt,sum):
    num[sum]=1
    if cnt == n:
        return
    for i in range(n):
        if not visited[i]:
            visited[i]=1
            num[ary[i]]=1
            recur(visited,cnt+1,sum+ary[i])
            visited[i]=0

recur([0]*(n+1),0,0)

for idx in range(1,100001):
    if num[idx]==0:
        print(idx)
        break

 

비트마스크는 수행시간이 되게 빨라서 위처럼 오랜시간이 걸리지 않지만 이진수 계산기법을 다배우긴 했지만 익숙하지 않아서 부분집합 원소를 조회하는 방식을 이해하는데 시간이 좀 걸렸다.

먼저 기본적으로 여기서 쓰인 연산자 중

a << b는 a를 b만큼 왼쪽으로 이동시키는 걸 의미하고 &연산은 두개의 값이 1인 경우에 1이 반환된다는 것을 의미한다.

이제 문제 풀이로 넘어가서 일단 원소의 개수가 n일 경우 부분집합의 개수는 2^n이기 때문에 1을 왼쪽으로 n만큼 이동시킨 값만큼 for문을 반복하였다.

그 이후의 과정은 2진수를 이용한 예시를 보면 쉽게 이해가 간다.

ex) 문제에서 주어진 예제 1번처럼 list가 [5,1,2]일때

i의 값이 5일 경우로 예를 들자면 (2진수로 나타내면 0b0101) 즉, j가 0과 2인 경우가 i& (1<<j)의 값이 1인 true로 리턴되고

이는 5와 2가 이 부분집합에 포함된다는 것을 의미한다.

같은 방식으로

i = 0 -> []     #0b0000
i = 1 ->[5] j = 0      #0b0001
i = 2 ->[1] j = 1      #0b0010
i = 3 ->[5, 1] j = 0, j = 1     #0b0011
i = 4 ->[2] j = 2     #0b0100
i = 5 ->[5, 2] j = 0, j = 2      #0b0101
i = 6 ->[1, 2] j = 1, j = 2      #0b0110
i = 7 ->[5, 1, 2] j = 0, j = 1, j = 2      #0b0111

그리고 num list를 2000000만큼 size를 정한 이유는 n이 최대 20이고 원소의 값은 최대 100000이기 때문에 그렇게 초기화했다.

import sys
cnt=[]
input=sys.stdin.readline
num = [0]*2000000
n = int(input())
ary = list(map(int,input().split()))
num=[0]*2000001
def solution(ary,n):
    for i in range(1 << n):
        subseq = []
        for j in range(n):
            if i & (1 << j):
                subseq.append(ary[j])

        if len(subseq)>0:
            num[sum(subseq)]=1

solution(ary,n)
for idx in range(1,2000001):
    if not num[idx]:
        print(idx)
        break