문제 / 합이 같은 부분집합(DFS) / Python 파이썬

 

문제 제목: 합이 같은 부분집합(DFS)

 

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

예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.

 

▣ 입력설명 첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다. 두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않는다.

 

▣ 출력설명 첫 번째 줄에 “YES" 또는 ”NO"를 출력한다.

 

▣ 입력예제 1

6

1 3 5 6 7 10

 

▣ 출력예제 1

YES

---

풀이

def DFS(L,sum):
    if L == n:
        if sum == (total-sum):
            # 두개의 부분 집합의 뭔소의 합이 같다
            print("YES")
            sys.exit(0) # 프로그램 전체를 종료한다.
    else:
        DFS(L+1, sum + a[L]) #왼쪽 노드로 간다 (a 리스트에서 L이 가리키는 것을 넣고 감)
        DFS(L+1, sum) # 왼쪽 노드로 간다. (a 리스트 사용X)

if __name__ == "__main__":
    dfs_list = []
    n = int(input())
    a = list(map(int,input().split()))
    total = sum(a)
    DFS(0,0)
    print("NO") # 참이 되는 경우가 없는 경우 No를 출력, 참이되면 프로그램이 종료됨

** sum > total // 2 (주어진 집합의 원소들의 합보다 커지면 계산할 필요가 없어진다.)

 

예를들어 total = 13 이면

sum // 2 = 6

sum = total - sum

        = 13 - 6 = 7

sum != total 

이라서 

 

조건문을 하나 더 걸어준다.

if sum > total // 2:
    return

 

모범답안

def DFS(L,sum):
    if sum > total // 2:
        return
    if L == n:
        if sum == (total-sum):
            # 두개의 부분 집합의 뭔소의 합이 같다
            print("YES")
            sys.exit(0) # 프로그램 전체를 종료한다.
    else:
        DFS(L+1, sum + a[L]) #왼쪽 노드로 간다 (a 리스트에서 L이 가리키는 것을 넣고 감)
        DFS(L+1, sum) # 왼쪽 노드로 간다. (a 리스트 사용X)

if __name__ == "__main__":
    dfs_list = []
    n = int(input())
    a = list(map(int,input().split()))
    total = sum(a)
    DFS(0,0)
    print("NO")

---