[파이썬 알고리즘 문제풀이 입문] 완전탐색 (백트랙킹, 상태트리와 CUT EDGE) / DFS(깊이우선탐색) 기초 - 합이 같은 부분집합 (DFS)

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다.

 

 

 

문제

N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 'YES'를 출력하고, 그렇지 않으면 'NO'를 출력하는 프로그램을 작성하세요.
둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어야 합니다.

 

 

 

 

풀이

• 답안 : Python

import sys
input = sys.stdin.readline

def DFS(index, sum):
    # total 절반을 넘으면 의미가 없음 (시간복잡도 단축)
    if sum > (total//2):
        return
    
    # 종료 지점
    if index == N:
        # total - sum : 내가 만든 부분집합의 반대(나머지) 부분집합의 합
        if sum == (total-sum):
            print("YES")
            sys.exit(0) # 프로그램 자체를 종료
    else:
        DFS(index+1, sum+numbers[index]) # 해당 인덱스의 값 사용O
        DFS(index+1, sum) # 해당 인덱스의 값 사용X

N = int(input())
numbers = list(map(int, input().split()))
total = sum(numbers)
DFS(0, 0)
print("NO")

그림으로 이해해보자.

 

- 위의 문제에 대한 상태트리를 그림으로 표현해보았다.

- DFS(index, sum) → numbers의 해당 index의 값을 사용하기 위해 필요 / 부분집합의 합을 나타내기 위해 sum 필요

- 한 쪽 부분집합(A)을 정하게 되면, 다른 한 쪽(B)은 자동으로 정해지게 된다.

   때문에 한 쪽 부분집합(A)의 합을 구하게 되면, 다른 한 쪽(B)의 합은 numbers의 전체 합 - 한 쪽 부분집합(A)의 합을 빼주면 된다.

- numbers[1, 3, 5, 6, 7, 10] 이런 상태에서 경우의 수는 2^6개가 나올 수 있다.

   이걸 다 따지면 시간복잡도가 높아지기 때문에, total 절반이 넘게되면 바로 return 해서 "NO"가 출력되게 한다.