합이 같은 부분집합(DFS)

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

 

둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어야 함

예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재

 

▣ 입력설명

첫 번째 줄에 자연수 N(1<=N<=10)

두 번째 줄에 집합의 원소 N개

각 원소는 중복되지 않음

 

▣ 출력설명

첫 번째 줄에 “YES" 또는 ”NO"를 출력

 

▣ 입력예제

6

1 3 5 6 7 10

 

▣ 출력예제

YES

---

내가 쓴 코드

import sys
sys.stdin = open("input.txt",'rt')

def DFS(idx, current_sum):
    global result
    if result == 1:
        return

    if idx == N:
        if current_sum == goal:
            result = 1
            return
    else:
        DFS(idx+1,current_sum + lst[idx])
        DFS(idx+1,current_sum)



if __name__ == '__main__':
    N = int(input())
    current_sum = 0
    lst = list(map(int, input().split()))

    if sum(lst) % 2 != 0:
        print("NO")
    else:
        goal = sum(lst)//2
        result = 0

        DFS(0,current_sum)

        if result == 1:
            print("YES")
        else:
            print("NO")

 

모범답안

#모범답안
import sys
sys.stdin = open("input.txt",'rt')

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])
        DFS(L+1, sum)


if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))

    total = sum(a)
    DFS(0,0)
    print("NO")

 

느낀점

1. DFS의 흐름을 이해해가는것 같다! 상태트리를 그려보며 진행하니 확실히 수월하다.
2. 효율적!인 코드를 짜도록 노력해야겠다.
내 코드에서도
어떤 원소들이 합을 구성하는지 알 필요는 없으니까
subset을 두지 않고 current_sum으로 합만 트래킹 하는 것이 훨씬 효율적이다.
3. sys.exit(0) 썻으면 전역변수로 result 안써도 가능했겠다!
sys.exit(0)에서 매개변수 0은 정상종료를 나타냄

 

---

 

다시 풀어보기

#다시 풀어보기
import sys
sys.stdin = open("input.txt",'rt')

def DFS(idx,current_sum):
    if current_sum > total//2:
        return
    if idx == N:
        if current_sum == total//2:
            print("YES")
            sys.exit(0)
    else:
        DFS(idx+1, current_sum+lst[idx])
        DFS(idx+1, current_sum)

if __name__ == "__main__":
    N = int(input())
    lst = list(map(int, input().split()))
    total = sum(lst)
    if total%2 != 0:
        print("NO")
    else:
        DFS(0,0)
        print("NO")