[문제]
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
[풀이]
import sys
def dfs(l, sum): # l: 인덱스 번호, sum: 부분집합 원소의 총 합
if sum > total//2: # 부분집합의 합이 나머지 총합보다 커질 경우 볼 필요 없음
return
if l ==n: # 종료 지점
if sum == (total-sum): # 부분집합의 총합이 나머지와 같다면
print("YES")
sys.exit(0) # 프로그램 종료
else:
dfs(l+1, sum+m[l]) # list m의 인덱스 번호가 l인 벨류 값을 부분집합의 원소로 사용
dfs(l+1, sum) # list m의 인덱스 번호가 l인 벨류 값을 부분집합으로 사용하지 않겠다는 의미
n = int(input())
m = list(map(int, input().split()))
total = sum(m)
dfs(0, 0)
print("NO") # 재귀가 다 돌고 끝나면 같은게 없으므로 NO 출력
[내용]
- 상태트리를 어떻게 그려야할지 고민이 많았다. 지난번 처럼 체크 테이블을 하자니 시간복잡도가 너무 높게 나올 것 같았다..
- 그래서 결국 풀이를 또 봐버렸다... 이번에는 DFS 함수 인자에 인덱스, 부분집합의 합을 넣어주어서 해당 인덱스의 원소를 부분집합에 포함시키는지 아닌지에 따라 상태트리 갈래 길을 결정했다.
=> 인덱스의 원소는 계속 증가시키되, 부분합에 해당 원소가 누적해서 더해지면 해당 원소를 부분집합에 포함시켰다는 의미이고, 이전 누적값을 그대로 해서 간다면 부분집합에 포함시키지 않는다는 것을 의미!
<시간복잡도 줄이기>
1. sys.exit(0): 프로그램 아예 종료
2. 1을 사용하지 못할 경우엔 flag 라는 새로운 변수로 처리
def dfs(l, sum): # l: 인덱스 번호, sum: 부분집합 원소의 총 합
global flag
if flag:
return
if sum > total // 2: # 부분집합의 합이 나머지 총합보다 커질 경우 볼 필요 없음
return
if l ==n: # 종료 지점
if sum == (total-sum): # 부분집합의 총합이 나머지와 같다면
print("YES")
flag = True
else:
dfs(l+1, sum+m[l]) # list m의 인덱스 번호가 l인 벨류 값을 부분집합의 원소로 사용
dfs(l+1, sum) # list m의 인덱스 번호가 l인 벨류 값을 부분집합으로 사용하지 않겠다는 의미
n = int(input())
m = list(map(int, input().split()))
total = sum(m)
flag = False
dfs(0, 0)
if not flag:
print("NO") # 재귀가 다 돌고 끝나면 같은게 없으므로 NO 출력'Coding Test > Python' 카테고리의 다른 글
| [Python] 달리기 경주 (0) | 2023.05.05 |
|---|---|
| [python] 바둑이 승차(DFS) (0) | 2023.03.24 |
| [python] 부분집합 구하기(DFS) (0) | 2023.03.19 |
| [python] 재귀함수를 이용한 이진수 출력 (0) | 2023.03.15 |
| [python] 가장 큰 수 (0) | 2023.02.26 |