[백준] 14225번 : 부분수열의 합 (파이썬)

 

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

14225번: 부분수열의 합

 

 

---

 

 

<나의 풀이>

# 모듈 추가
from collections import Counter
from itertools import combinations

# 입력
n = int(input())
s = list(map(int, input().split()))

# 입력값의 모든 조합을 구한 후, 조합 별 합을 새로운 리스트에 추가함
sum_list = []
for i in range(1, n+1):
    combin = list(combinations(s, i))
    for j in combin:
        sum_list.append(sum(j))

# 정렬
sum_list.sort()

# 없는 번호를 찾기 위한 체크 리스트
check_num = [i for i in range(1, sum_list[-1]+2)]

# check_num에서 sum_list를 빼주면 sum_list에 없는 번호만 result에 담김
result = Counter(check_num) - Counter(sum_list)

# result는 Counter이므로 리스트로 변환 후 맨 처음 키값만 출력 
print(list(result.keys())[0])

 

 

<다른 사람의 풀이>

# asm9677님 코드

input()
a=0
for i in [*sorted(map(int,input().split()))]:
    if a+1<i:break
    a+=i
print(a+1)
    
# <배운점> 
# => 접근법.. 짧은 코딩..

# zeebraa00님의 코드

n = int(input())
num = list(map(int,input().split()))
visited = [0]*10000000

def dfs(idx,sum) :
    if idx == n :
       return
    sum += num[idx]
    visited[sum] = 1
    dfs(idx+1, sum)
    dfs(idx+1, sum-num[idx])

dfs(0,0)
print(visited[1:].index(0)+1)

# <배운점> 
# => dfs를 이용하여 푼 점