다단계 칫솔 판매

문제해석

부모: 추천인
부모에게 10% 상납, 90%는 내가 가짐

• 특수조건

1. 10% 계산시 원단위에서 절삭(버림)
2. 10% 계산한 금액이 1원미만인 경우에는 상납안하고 걍 내가 다 가짐

밑에서 부터 위까지 탐색하면서 업데이트 -> DFS 생각하고 문제 시작
DFS는 자료구조를 잘 만드는게 중요
90%는 곱하는게 아니라 전체크기에서 10%를 절삭시킨값(정수)을 빼는 것임

자료구조

• seller와 amount가 짝궁
  ex> young이 12*100 = 1200 판매힘 올림
• enroll과 referral이 짝궁
  ex> john과 mary 부모는 루트("-"), edward의 부모는 mary
• result는?
  enroll과 짝궁

풀이

1) 탐색하기 위한 해시 생성

for i in range(0, len(enroll)):
        key_matching[enroll[i]]=i

이름을 키로하고 인덱스를 값으로 해서, 이름을 가지고 인덱스를 찾도록
enroll과 result는 짝궁임 근데 둘다 기준을 인덱스값으로 하니깐...

• enroll[0] -> john
• result[0] -> john의 돈

2) Seller 하나씩 for문 돌려서 업데이트 시작

result=[0]*(len(enroll))    
    for i in range(0, len(seller)):
        now_amount = amount[i]*100
        result = dfs(key_matching, enroll, referral, seller[i], now_amount, result)

3) DFS

def dfs(key_matching, enroll, referral, name, now_amount, result):
    index = key_matching[name]
    if int(now_amount*0.1)<1:
        result[index]+=int(now_amount)
        return result
    else:
        result[index]+=int(now_amount)-int(now_amount*0.1)
    
    if referral[index]=="-":
        return result
    else:
        return dfs(key_matching, enroll, referral, referral[index], int(now_amount*0.1), result)
    

1. 이름으로 index를 뽑는다.
2. 만약 현재가격의 10%가 1보다 작으면, 그냥 그대로(100%) 더해줌
3. 아니면 90%를 더해줌
4. 만약 부모가 루트("-")면 dfs 종료(return)
5. 일반적 부모면 바로 여전히 dfs 탐색
   가. 이제 name에 부모의 name 들어감
   -> referral[index]
   나. 현재 가격도 10%곱한값이 인자로 들어감