-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
문제 6-4 <합이 같은 부분집합>
20.05.28 20:52 작성 조회수 71
0
안녕하세요 선생님. 강의 잘 듣고있습니다.
문제 6-4번 풀던 중에 궁금한점이 생겼는데요.
dfs 함수의 if문에서 조건을 충족하면 True를 리턴하고, 맨 마지막에 있는 if문을 통해 yes를 프린트 하려고 했는데,
None이 출력되는 이유가 궁금합니다!
```
# 합이 같은 부분집합
import sys
sys.stdin = open('input4.txt', 'r')
n = int(input())
fo = list(map(int, input().split()))
result = [0]*n
def dfs(k):
summ = 0
if k == n :
for i in range(n):
if result[i] == 1 :
summ += fo[i]
if summ*2 == sum(fo) :
return True
else :
result[k] = 1
dfs(k+1)
result[k] = 0
dfs(k+1)
print(dfs(0))
if dfs(0):
print("YES")
else :
print("NO")
```
답변을 작성해보세요.
0
김태원
지식공유자2020.05.29
감사합니다^^
def DFS(n):
if n==5:
return True
else:
DFS(n+1)
if __name__=="__main__":
print(DFS(0))
위 코드는 DFS(5)만 True를 리턴받고 그 값이 DFS(0)까지 전달이 되지 않아 DFS(0)은 None값을 갖는 코드입니다.
def DFS(n):
if n==5:
return True
else:
return DFS(n+1)
if __name__=="__main__":
print(DFS(0))
위 코드는 DFS(5)가 True를 리턴받고, DFS(4)는 DFS(5)를 린턴받고 하면서 초종적으로 DFS(0)은 DFS(1)를 리턴받아 True를 리턴받게 됩니다.
이 문제처럼 함수 호출이 여러갈래로 이루어질 때는 함수가 값을 리턴받는게 아리라 변수를 사용해서 해결합니다. (exit() 없이 해결할 때)
def DFS(L):
global res
if res: return
if L == n:
Sum=0
for i in range(n):
if result[i]==1:
Sum+=a[i]
if Sum*2==sum(a):
res=True
else:
result[L]=1
DFS(L+1)
result[L]=0
DFS(L+1)
if __name__ == '__main__':
n = int(input())
a = list(map(int, input().split()))
result=[0]*n
res=False
DFS(0)
if res:
print("YES")
else:
print("NO")
답변 1