[백준] 1182 : 부분수열의 합 (Python)

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

풀이 코드

---

from collections import defaultdict
count_dict = defaultdict(int)

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

def count(temp_sum, idx, check:bool):
    global val_list
    if check:
        temp_sum += val_list[idx]
    if idx==len(val_list)-1:
        count_dict[temp_sum]+=1
    else:
        count(temp_sum, idx+1, True)
        count(temp_sum, idx+1, False)

count(0, 0, True)
count(0, 0, False)

count_dict[0]-=1

print(count_dict[S])

풀이 해설

---

모든 조합에 대한 합을 키(key) 값으로 갖는 딕셔너리를 만들어서
입력받은 S의 조합이 몇개가 가능한지 정답을 구하도록 풀어보았습니다

사용한 defaultdict(int)는 접근하려는 키에 해당하는 값이 존재하지 않을 경우
0을 기본값으로 갖는 원소를 자동적으로 생성해주는 딕셔너리입니다

위 풀이의 경우 Depth First Search (DFS) 기반으로 조합을 생성해 문제풀이를 진행했는데
소요 시간이 540ms로 다른 제출자에 비해 상당히 오래 걸린 편이었습니다

소요 시간이 짧은 제출자들의 경우 백트래킹이라는 알고리즘을 이용한 것으로 보여지는데
해당 부분에 대해서는 추가적으로 공부해봐야겠습니다