[BOJ] 14225번 부분수열의 합 / 사용언어 : 파이썬(python)

※ 문제링크

14225번: 부분수열의 합

해당문제는 모든 경우의 수를 탐색해서 결과값을 확인하여 해결할 수 있는 문제였다. 다만, 숫자들의 조합에서 순서는 의미를 가지지않았기에 순열이 아닌 조합의 형태로 코드를 작성해야했다. 해당 조건을 고려하여 문제를 해결하였으며, 자세한 풀이방법과 코드는 아래와 같다.

1. 입력받은 값들을 리스트형태로 저장해준다.

2. 입력될 수 있는 리스트의 길이와 값을 바탕으로 방문여부를 확인할 리스트를 작성하고, 입력값의 조합을 바탕으로 해당하는 숫자들의 합의 해당여부를 체크할 리스트를 만들어준다.

3. 숫자들의 조합을 작성할 DFS함수를 작성하여 결과값을 확인하고, 모든 조합값을 확인 후 Index함수를 이용하여 체크되지 않은 최솟값을 구한 후 출력한다.

 

N = int(input())
S = list(map(int, input().split()))
result = [0] + [-1 for _ in range(2000000)]
arr = []
visited = [False for _ in range(N+1)]

def dfs(start):
    check = sum(arr)
    result[check] = check

    for i in range(start, N):
        if visited[i]:
            continue

        arr.append(S[i])
        visited[i] = True
        dfs(i)
        arr.pop()
        visited[i] = False
    return

dfs(0)
print(result.index(-1))

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.