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

※ 문제링크

1182번: 부분수열의 합

해당 문제는 DFS와 백트래킹을 활용하여 모든 경우의 수를 탐색하여 풀 수 있는 문제였다. 기본적인 풀이원리는 입력받은 값들을 바탕으로 길이가 1인 행렬부터 길이가 N인 행렬까지 가능한 모든 경우의 수를 탐색하고 그 합이 요구치와 같으면 값을 더하는 방식으로, 브루스포트 알고리즘과 DFS를 이해하고 있으면 비교적 쉽게 해결할 수 있는 문제였다. 자세한 풀이방법과 코드는 아래와 같다.

1. 입력받은 값들을 저장하고, 숫자들을 정수로 변환하여 리스트형태로 저장해준다.

2. 숫자들의 부분수열들을 체크할 리스트를 할당하고, 숫자별 방문경로를 확인할 방문경로 리스트를 생성한다.

3. DFS와 백트래킹의 원리를 활용한 DFS함수를 작성하여 경우의 수 중 조건에 만족하는 수열의 개수를 카운트한다.

4. DFS함수를 0부터 시작하여 종료후 결과값을 출력한다.

 

N, S = map(int, input().split())
numbers = list(map(int, input().split()))

arr = []
visited = [False for _ in range(N)]
ans = 0
def dfs(start):
    global ans
    if sum(arr) == S and len(arr) != 0:
        ans += 1
    
    for i in range(start, N):
        if visited[i]:
            continue

        arr.append(numbers[i])
        visited[i] = True
        dfs(i+1)
        arr.pop()
        visited[i] = False
    
    return

dfs(0)
print(ans)

 

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