문제

https://school.programmers.co.kr/learn/courses/30/lessons/77486

풀이

아이디어

• 별다른 알고리즘은 없고 defaultdict와 재귀함수를 잘 써먹으면 되는 문제인 것 같다.
• 재귀를 돌려서 트리의 맨 밑에서부터 가장 위까지 번 금액에 대해 문제 조건대로 전파시켜 주는 것인데, 꼭 재귀함수 아니어도 while문으로 반복할 수 있다.
• 금액 1원단위 절사 관련해서 조금 헷갈리는 부분이 있긴 했으나 예제를 보고 잘 구현해주면 된다.

코드

from collections import defaultdict
import math
def solution(enroll, referral, seller, amount):
    #가장 먼저 부모가 누구인지에 대한 그래프를 defaultdict로 만든다
    parent = defaultdict(str)
    for child, par in zip(enroll, referral):
        parent[child] = par if par != "-" else "minho"
    parent['minho'] = '-'
    
    #벌어들인 수익을 저장하는 defaultdict
    income = defaultdict(int)
    for en in enroll:
        income[en] = 0
    
    def saveIncome(name, amount):
        if parent[name] != "-":
            if amount >= 10:
                big = math.ceil(amount * 0.9)
                income[name] += int(big)
                saveIncome(parent[name], amount - int(big))
            else:
                income[name] += amount
    
    for name, am in zip(seller, amount):
        saveIncome(name, am * 100)
    
    return list(income.values())