(Python)백준 코딩테스트 연습 - 부분수열의 합(1182)

1. 문제

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

1182번: 부분수열의 합

2. 풀이

import sys
input = sys.stdin.readline

# n : 입력받는 정수 개수, s : 부분 수열의 합이 되야하는 수
n, s = map(int, input().split())

# n_l : 입력받은 정수 리스트
n_l = list(map(int, input().split()))
n_l.sort()

sequen_cnt = 0
def dfs_count(n_l, s_l, depth):
    
    global sequen_cnt
    if len(s_l) > 0 and sum(s_l) == s:
        sequen_cnt += 1
        
    
    for i in range(depth, n):
        s_l.append(n_l[i])
        dfs_count(n_l, s_l, i + 1)
        s_l.pop()
dfs_count(n_l, [], 0)
print(sequen_cnt)

3. 후기

 - 위 문제는 재귀를 사용한 방법을 이용하여 해결하였다.

 아직 백트래킹 알고리즘이 익숙하지는 않지만, 차후 관련 문제를 통해 해당 알고리즘에 친숙해져야할 필요성을 느꼈다.