[백준] 14225번 부분수열의 합 - Python / 알고리즘 중급 1/3 - 브루트 포스 - 재귀 (연습)

---

---

---

💡 문제

수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오.

예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 수 있다. 하지만, 4는 만들 수 없기 때문에 정답은 4이다.

입력

첫째 줄에 수열 S의 크기 N이 주어진다. (1 ≤ N ≤ 20)

둘째 줄에는 수열 S가 주어진다. S를 이루고있는 수는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 출력한다.

---

💭 접근

먼저 길이기 n인 mask 리스트에 True와 False로만 이루어진 중복 순열을 만든 뒤, mask가 True인 index의 숫자만 더해준다.

이후 더한 값을 ans_list 리스트에 append 해주고, 모든 부분 수열의 합이 구해지면 리스트를 정렬한 뒤 1부터 len(ans_list) (부분 수열의 합의 개수) 만큼 반복하며 가장 작은 자연수를 찾는다.

---

📒 코드

def dfs(depth):
    if depth == n:
        tmp = 0
        for i in range(n):
            if mask[i]:
                tmp += s[i]
        ans_list.append(tmp)
        return

    for bit in bits:
        mask.append(bit)
        dfs(depth + 1)
        mask.pop()

n = int(input())
s = list(map(int, input().split()))
bits = [True, False]

ans_list = []
mask = []
dfs(0)

ans_list = sorted(list(set(ans_list)))
for i in range(len(ans_list)):
    if i != ans_list[i]:
        print(i)
        break
else:
    print(len(ans_list))

---

💭 후기

1182번 부분수열의 합 문제와 유사한 문제.

---

🔗 문제 출처

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

---