[Baekjoon] 1182번 : 부분수열의 합 (Python, 백트래킹)

[Baekjoon] 1182번 : 부분수열의 합 (Python, 백트래킹)

 

목차

 

 

 

 

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

1182번: 부분수열의 합

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

시간 초과 - 방법 1 - 코드 길이 473B

 

일반적인 백트래킹이라하면 방문처리를 통한 다음 step에서의 처리와 함께 종료 조건을 설정하는 것이다.

그러나 그 경우 시간 초과를 맞이하게 된다....

 

def dfs(idx, total):
    global s
    if idx >= 1 and total == s:
        tmp = ' '.join(map(str, visit))
        if tmp not in o:
            o.append(tmp)
        return

    for i in range(idx, n):
        if not visit[i]:
            visit[i] = 1
            dfs(idx+1, total + l[i])
            visit[i] = 0


import sys
input = sys.stdin.readline

n,s = map(int, input().split())
l = list(map(int, input().split()))
visit = [0]*n
o = []
dfs(0, 0)
print(len(o))

 

방법 2 - 메모리 30840KB / 시간 504ms / 코드 길이 316B

 

방법 1은 고전적인 방법이라면 이 방법은 트리 구조를 생각하게하는 방법이다.

예제 1과 같이 내가 -7, -3, -2, 5, 8이 존재한다고 가정했을 때 부분 집합의 합을 구하고 싶다. 

이때 나는 -7을 선택할 수도 하지 않을 수도 있다.

나머지 -3, -2, 5, 8에 대해서도 마찬가지이다.

이에 백트래킹으로 각 위치별 idx를 활용하여 나는 -7을 가져갈 것이다와 가져가지 않을 것이다에 해당하는 dfs를 구성한다.

그리고 종료 문구는 idx가 주어진 idx를 넘어갈 때로 설정하고 그 동안 s와 일치하는 것들에 대해서는 개수를 지속적으로 계산한다.

 

이렇게 하면 문제 풀이가 완료된다. 

 

def dfs(idx, total):
    global cnt

    if idx >= n:
        return
    total += l[idx]
    if total == s:
        cnt += 1

    dfs(idx+1, total)
    dfs(idx+1, total - l[idx])


import sys
input = sys.stdin.readline

n,s = map(int, input().split())
l = list(map(int, input().split()))
cnt = 0
dfs(0, 0)
print(cnt)