[프로그래머스] 다단계 칫솔 판매(Python)

zioo·2022년 11월 24일
0

문제

다단계 칫솔 판매

문제 해설

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

0개의 댓글