[Python] 14225 - 부분수열의 합 (실버1)

1. 문제 설명

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

14225번: 부분수열의 합

 

---

2. 아이디어

처음 알고리즘을 공부할 때 함수명을 dfs나 dijkstra처럼 쓰지 않는 사소한 반항을 했었는데,

그땐 그게 멋있어 보였나..덕분에 블로그에 정리하는데 무슨 의도로 썼었는지 헷갈린다.

 

N의 범위가 고작 해봐야 20이하이므로 brute-force로 끝내버렸다.

모든 경우의 수를 조합하여 가능한 결과값을 모두 리스트에 때려넣은 후에 정렬시킨다.

자료형 set으로 바꿨었던 이유는 중복을 제거하기 위해서 사용했던 것으로 기억한다.

 

그러고 1부터 모든 값을 순회하며 리스트에 들어있지 않은 값을 찾아내 출력하면 끝난다.

 

---

3. 코드

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

def fill_list(case, value, deepth):
    if deepth == n:
        return
    value += s[deepth]
    case.append(value)
    fill_list(case, value, deepth + 1)
    fill_list(case, value - s[deepth], deepth + 1)

def solution():
    case = []
    if n != len(s): exit()
    fill_list(case, 0, 0)
    case = list(set(case))
    case.sort()
    case.append(0)
    for nbr in range(1, len(case) + 1):
        if nbr != case[nbr - 1]:
            print(nbr)
            return
    
solution()