다단계 칫솔 판매

• 특별한 알고리즘 없이 그냥 그대로 구현하면 된다..
• 자식이 업데이트될때 부모들도 똑같은 값이 증가된다면, 오일러 트리 테크닉과 세그먼트 트리를 이용하여 효율적으로 푸는 방법을 고민해 볼수 있겠지만, 이 문제는 그렇게 하기도 쉽지 않거니와 그렇게 할 필요도 없다. 이익이 최대 100*100 = 10000원이기 때문에, 10%씩 부모에게 떼어주는 것을 반복하면, 업데이트 되는 노드의 갯수는 최대 5개뿐이다. 따라서 한개의 쿼리에 5개 이하의 노드만 업데이트해주면 되므로 그냥 O(1)으로 생각할수 있다. n개의 노드로 트리를 만드는 데에는 O(n), m개의 쿼리를 각각 O(1)에 처리하는 데에는 O(m). 총 시간복잡도는 O(n+m).

"""Solution code for "Programmers 77486. 다단계 칫솔 판매".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/77486
- Solution link: http://www.teferi.net/ps/problems/programmers/77486
"""

import collections

COST = 100


def solution(enroll, referral, seller, amount):
    parents = {child: parent for child, parent in zip(enroll, referral)}
    parents['-'] = '-'
    profits = collections.defaultdict(int)

    for s, a in zip(seller, amount):
        profit = a * COST
        member = s
        while profit > 0:
            profit_to_referral = profit // 10
            profits[member] += profit - profit_to_referral
            profit, member = profit_to_referral, parents[member]

    return [profits[x] for x in enroll]