[Python/알고리즘] 다단계 칫솔 판매 (Lv.3)

문제 설명

민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, 조직을 운영하던 민호는 조직 내 누가 얼마만큼의 이득을 가져갔는지가 궁금해졌습니다. 예를 들어, 민호가 운영하고 있는 다단계 칫솔 판매 조직이 아래 그림과 같다고 합시다.

민호는 center이며, 파란색 네모는 여덟 명의 판매원을 표시한 것입니다. 각각은 자신을 조직에 참여시킨 추천인에 연결되어 피라미드 식의 구조를 이루고 있습니다. 조직의 이익 분배 규칙은 간단합니다. 모든 판매원은 칫솔의 판매에 의하여 발생하는 이익에서 10% 를 계산하여 자신을 조직에 참여시킨 추천인에게 배분하고 나머지는 자신이 가집니다. 모든 판매원은 자신이 칫솔 판매에서 발생한 이익 뿐만 아니라, 자신이 조직에 추천하여 가입시킨 판매원에게서 발생하는 이익의 10% 까지 자신에 이익이 됩니다. 자신에게 발생하는 이익 또한 마찬가지의 규칙으로 자신의 추천인에게 분배됩니다. 단, 10% 를 계산할 때에는 원 단위에서 절사하며, 10%를 계산한 금액이 1 원 미만인 경우에는 이득을 분배하지 않고 자신이 모두 가집니다.

예를 들어, 아래와 같은 판매 기록이 있다고 가정하겠습니다. 칫솔의 판매에서 발생하는 이익은 개당 100 원으로 정해져 있습니다.

판매원판매 수량이익금

young	12	1,200 원
john	4	400 원
tod	2	200 원
emily	5	500 원
mary	10	1,000 원

판매원 young 에 의하여 1,200 원의 이익이 발생했습니다. young 은 이 중 10% 에 해당하는 120 원을, 자신을 조직에 참여시킨 추천인인 edward 에게 배분하고 자신은 나머지인 1,080 원을 가집니다. edward 는 young 에게서 받은 120 원 중 10% 인 12 원을 mary 에게 배분하고 자신은 나머지인 108 원을 가집니다. 12 원을 edward 로부터 받은 mary 는 10% 인 1 원을 센터에 (즉, 민호에게) 배분하고 자신은 나머지인 11 원을 가집니다. 이 상태를 그림으로 나타내면 아래와 같습니다.

 

 

 

풀이 포인트

수익이 발생하면 상위 요소에게 10%를 나눠준다.

하위 요소의 수익을 받은 상위 요소는 받은 금액의 10%를 다시 상위 요소에게 준다. 이를 반복한다.

10원 미만이라면 상위 요소 존재 여부에 관계없이 본인이 남은 금액을 모두 가지고 반복을 끝낸다.

상위 요소가 "-"이라면 반복을 끝낸다. (center의 금액은 출력할 필요없다)

 

* dict(zip(list, list)) 함수를 사용해 참조가 쉽도록 object로 만들어준다.

* list(dict.values())를 사용하면 value만 뽑아 list로 반환해준다.

* 10%를 절사한 경우 상위로 올라가는 금액은 정수 내림(math.floor()), 현재 요소가 받는 금액은 정수 올림(math.ceil())이 필요하다.

 

 

해결 코드

import math

def solution(enroll, referral, seller, amount):

    parentTree = dict(zip(enroll, referral))
    answer = dict(zip(enroll, [0 for i in range(len(enroll))]))

    
    for i in range(len(seller)):
        earn = amount[i] * 100
        target = seller[i]

        while True :
            if earn < 10 : #10원 단위 이하라면 모두 받고 레퍼럴 종료
                answer[target] += earn
                break
            else : #10% 레퍼럴을 제외하고 받는다
                answer[target] += math.ceil(earn * 0.9)
                if parentTree[target] == "-": #상위가 없다면 종료
                    break
                earn = math.floor(earn*0.1)
                target = parentTree[target]
                    
    return list(answer.values())

특별한 개념없이 dict와 일부 함수만 사용하면 어렵지 않은 문제이다.

answer[i]라고 작성하는 바람에 디버깅에 많은 시간이 소요됐다. 오타에 주의하자.