77486: 다단계 칫솔 판매

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

---

1. 문제

• 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, 조직을 운영하던 민호는 조직 내 누가 얼마만큼의 이득을 가져갔는지가 궁금해졌습니다. 예를 들어, 민호가 운영하고 있는 다단계 칫솔 판매 조직이 아래 그림과 같다고 합시다.
• 
• 민호는 center이며, 파란색 네모는 여덟 명의 판매원을 표시한 것입니다. 각각은 자신을 조직에 참여시킨 추천인에 연결되어 피라미드 식의 구조를 이루고 있습니다. 조직의 이익 분배 규칙은 간단합니다. 모든 판매원은 칫솔의 판매에 의하여 발생하는 이익에서 10% 를 계산하여 자신을 조직에 참여시킨 추천인에게 배분하고 나머지는 자신이 가집니다. 모든 판매원은 자신이 칫솔 판매에서 발생한 이익 뿐만 아니라, 자신이 조직에 추천하여 가입시킨 판매원에게서 발생하는 이익의 10% 까지 자신에 이익이 됩니다. 자신에게 발생하는 이익 또한 마찬가지의 규칙으로 자신의 추천인에게 분배됩니다. 단, 10% 를 계산할 때에는 원 단위에서 절사하며, 10%를 계산한 금액이 1 원 미만인 경우에는 이득을 분배하지 않고 자신이 모두 가집니다.판매원판매 수량이익금

  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 원을 가집니다. 이 상태를 그림으로 나타내면 아래와 같습니다.
• 예를 들어, 아래와 같은 판매 기록이 있다고 가정하겠습니다. 칫솔의 판매에서 발생하는 이익은 개당 100 원으로 정해져 있습니다.
• 자세한 그림에 대한 설명은 본문을 찾아보시길 권장드립니다.

---

2. 문제의 조건

• 1 <= len(enroll) <= 10,000
• len(referral) = len(enroll)
• 1 <= len(seller) <= 100,000
• len(amount) = len(seller)
• 칫솔 한개의 이익 = 100

 

---

3. 문제 접근

• 해당 그림을 보면 알 수 있듯 무조건 트리형태입니다.
  mary 밑에 3개의 자식이 있는 것으로 보아 이진트리는 아닙니다!!
  트리와 해당 유저에 대한 노드를 저장할 수 있는 dict이면 충분히 해결 가능하다고 바로 생각하였습니다.
  일반적으로 트리하면 부모와 자식 노드의 정보를 기억하지만 현재 문제에서 필요한 노드 정보는 자신의 이익, 자기 윗선(부모) 이 2가지 입니다.
  해당 문제는 트리를 잘 구성하는 것이 중요하다고 판단하였습니다.
• PS : 저의 풀이에선 디버깅을 쉽게 하기 위해서 name을 사용하였습니다.
  하지만 실제적으로 해결 할 때에는 name은 필요 없고 소스 중 부모를 판단하는 부분에선 name이 아니라 현재 노드의 부모가 None이면 최상위 트리 즉, 문제에서 나오는 "민호" 입니다.

 

---

4. 풀이 방법

• Node 정의
  노드는 (이름, 현재 이익, 부모 정보) 가 필요합니다.
• traceNode : 현재 자기의 부모를 추적합니다.
  만약 amount가 1보다 작으면 부모에게 줄 돈이 없으므로 종료합니다.
  만약 현재가 "민호"(소스풀이에선 center) 라면 모든 금액을 주고 추적을 종료합니다.
  
  자기의 이익 분배는 N에서 10퍼를 뺀 나머지 부분이므로
  my_amount = amount - (amount // 10) 입니다.
  그리고 부모에게 줘야 할 돈은 amount - my_amount가 됩니다.
• solution
  enroll에 나오는 사람들을 Node로 정의합니다.
  
  enroll과 referral을 zip으로 묶어서 한번에 수행합니다.
  만약 상위가 없다면 그것은 민호이므로 민호에게 연결합니다.
  만약 상위가 있다면 그 상위를 연결해줍니다.
  (좀 더 깔끔하게 리팩토링 하고 싶으시면 - 를 미리 부모 이름으로 치환해주면 됩니다.)
  
  seller, amoount를 zip으로 묶어서 한번에 수행합니다.
  amount *= 100 (칫솔 한개는 100원의 이익)
  traceNode를 이용하여 이익을 분배합니다.
  
  마지막으로 enroll 순서로 이익을 출력해줍니다.

 

---

5. 소스코드

• https://cjw-git.tistory.com/191

 

---

 

cjw.git@gmail.com