.PNG)
45. 합이 같은 부분집합(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
<내 풀이>
- 차집합의 성질을 이용해야 할 것 같다
- 그래서 a라는 집합에 입력받은 애들을 넣어준다 (키는 0, 1, 2, ..)
- 그런데 이전 문제와 같은 상태트리로 풀려고 하는데 있다는 표시를 어떻게 해줄 지가 고민
- 일단 먼저 부분집합의 모든 경우의 수를 구하고 싶어서 아래와 같이 식을 설정했었는데 그게 잘 나오지 않는다
- 만약 부분집합 다 나오게 하는 경우의 수 만들면 차집합이랑 그 안에서 합 비교해서 같으면 yes나오게 하고 아니면 no나오게 하려고 했었다
- 도저히 모르겠어서 풀이를 들어보려고 한다..
def DFS(x) :
if x==n:
for i in range(n) :
if s.get(i)!=0:
print(s.get(i), end=' ')
print()
return
else :
s[x]=s[x]
DFS(x+1)
s[x]=0
DFS(x+1)
if __name__=='__main__' :
#차집합 성질 이용하면 될 듯
n=int(input())
s=dict([(k,v) for k,v in enumerate(list(map(int, input().split())))])
DFS(0)
==>1 3 5 6 7 10
1 3 5 6 7
1 3 5 6
1 3 5 6
1 3 5
1 3 5
1 3 5
1 3 5
1 3
1 3
1 3
1 3
1 3
1 3
1 3
1 3
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
이런식으로 나온다 - 원인 발견해보기
<풀이>
- total 이라는 전체의 합을 지정해놓고 여기서 만들어진 부분집합을 뺐을 때,
서로 값이 같으면 옳은 것이다
- DFS(a의 인덱스 번호, 누적합)
def DFS(L,sum) :
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') #YES안나와서 프로그램이 종료가 안됐으면 NO출력하는 것
===> 여기서 시간복잡도를 더 줄인다면
- 내가 만든 sum이 total의 절반을 넘어섰다면, 이제 같은 경우는 없다고 보면 됨
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') #YES안나와서 프로그램이 종료가 안됐으면 NO출력하는 것
<반성점>
- DFS너무 어렵다 나에게 아직은.. 이번 챕터 다 돌고 꼭 철저하게 복습하고 넘어가자
<배운 점>
- DFS(L, sum) 이런식으로 설정해주는 것이 가능하다
- 이번에는 합을 누적해나가는 것
- 나는 차집합만을 생각했는데 그냥 전체합 (total) 에서 지금까지의 합만 빼줘도 알 수 있으니깐..
- 그렇다고 무턱대고 sum=total//2 라고 하면 안되는게 total이 홀수면 오류난다
