dfs 를 이용해서 풀 수 있었다.
단, 10% 를 계산할 때에는 원 단위에서 절사하며, 10%를 계산한 금액이 1 원 미만인 경우에는 이득을 분배하지 않고 자신이 모두 가집니다.
1 <= amount <= 100
위의 두 조건을 사용하면 시간 초과 문제를 해결할 수 있다.
최대로 벌 수 있는 돈은 10,000이기 때문에 부모 노드 한테 줄 돈이 없을 때 바로 재귀를 종료하도록 하면, 재귀의 최대 깊이가 5가 된다.
def solution(enroll, referral, seller, amount):
'''
칫솔 한 개 판매해서 얻어지는 이익
dfs를 사용
맨 위에는 민호가 있음
'''
total = {}
answer = []
graph = {}
for i in range(len(enroll)):
graph[enroll[i]]= referral[i]
total[enroll[i]] = 0
left = 0
def dfs(name,money) :
left = int(money*(0.1))
total[name] += money - left
## 이거를 백트래킹 해줘야 한다.
## 부모가 없을 때나 부모한테 떼줄 돈 없을 때 return
if graph[name] == "-" or left == 0 :
return
else :
dfs(graph[name],left)
for i in range(len(seller)):
dfs(seller[i],amount[i]*100)
for e in enroll :
answer.append(total[e])
return answer