[Baekjoon Online Judge] 백준 1182번 부분수열의 합(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1182번 부분수열의 합

(Python)

(글쓴날 : 2020.03.25)

 

---

* Baekjoon Online Judge, 백준 1182번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 1182번 부분수열의 합

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

---

2) 풀이 과정

N개의 정수로 이루어진 수열이 주어질 때 크기가 양수인 부분 수열의 합이 S가 되는 경우의 수를 구하는 문제입니다.

 

저의 경우, 브루트 포스 방식을 사용하기보단, DFS를 이용해 문제를 풀었습니다.

스택에 부분 수열을 저장하였고, 부분 수열의 합은 사실상 조합을 의미하므로 탐색 중인 index를 재귀 호출할 때 인자로 넘겨 순서만 바뀐 부분 수열들의 중복을 제거했습니다.

그렇게 완전 탐색을 하는 도중, 조건문으로 스택의 길이가 0이 아니고 합이 S인 경우의 횟수를 세어 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
 
def dfs(index, N, S, sequence):
    global answer
    global visit
    global stack
    
    if len(stack) != 0 and sum(stack) == S:
        answer += 1
 
    for i in range(index, N):
        if not visit[i]:
            stack.append(sequence[i])
            visit[i] = True
            dfs(i, N, S, sequence)
            stack.pop()
            visit[i] = False
 
 
N, S = map(int, input().split())
sequence = list(map(int, input().split()))
answer = 0
visit = [False] * N
stack = []
 
dfs(0, N, S, sequence)
print(answer)

---