[Level3] 다단계 칫솔 판매
25 Mar 2022다단계 칫솔 판매
문제
민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, 조직을 운영하던 민호는 조직 내 누가 얼마만큼의 이득을 가져갔는지가 궁금해졌습니다. 예를 들어, 민호가 운영하고 있는 다단계 칫솔 판매 조직이 아래 그림과 같다고 합시다.
민호는 center이며, 파란색 네모는 여덟 명의 판매원을 표시한 것입니다. 각각은 자신을 조직에 참여시킨 추천인에 연결되어 피라미드 식의 구조를 이루고 있습니다. 조직의 이익 분배 규칙은 간단합니다. 모든 판매원은 칫솔의 판매에 의하여 발생하는 이익에서 10% 를 계산하여 자신을 조직에 참여시킨 추천인에게 배분하고 나머지는 자신이 가집니다. 모든 판매원은 자신이 칫솔 판매에서 발생한 이익 뿐만 아니라, 자신이 조직에 추천하여 가입시킨 판매원에게서 발생하는 이익의 10% 까지 자신에 이익이 됩니다. 자신에게 발생하는 이익 또한 마찬가지의 규칙으로 자신의 추천인에게 분배됩니다. 단, 10% 를 계산할 때에는 원 단위에서 절사하며, 10%를 계산한 금액이 1 원 미만인 경우에는 이득을 분배하지 않고 자신이 모두 가집니다.
풀이
아직 DFS와 BFS 및 그래프를 막 배운 나에게는 어려운 문제였다 ㅠㅠ.. 막상 풀고나니 기본적인 DFS와 BFS에서 응용된 문제였지만..
enroll 에 등장하는 이름은 조직에 참여한 순서에 따릅니다.
해당 문구를 참고해 사진의 복잡한 트리구조는 깊이 순으로 enroll 배열이 주어지므로, 트리의 순서는 정해져 있다. 또한, referral 배열에서 enroll과 동일한 index 순으로 부모-자식의 관계를 알려준다.
HashMap<String, String> networkCompany = new HashMap<>();
HashMap<String, Integer> companyDepth = new HashMap<>();
그러므로 각각,
networkCompany의 HashMap에는 <Key:자식, Value:부모> companyDepth의 HashMap에는 <Key:자식, Value:들어간순서>
를 선언 해주면 주어진 값에 대한 트리구조를 만들 수 있다.
금액에 대한 계산식은 칫솔을 12개를 팔아 1200원의 수익을 남길시, 자식부터 부모까지
- (1200-120) 1080원분배 -> (120-12) 108원 분배 -> (12-1) 11원 분배
와 같은 순서로 분배 해주면 된다.
규칙에 따라서 계산식은 아래의 소스를 반복하게 된다.
result[companyDepth.get(clerk)] += money - money/10;
money = money/10;
이렇게 생성한 트리구조를 DFS를 이용해 탐색해 주면 된다. 주어진 두가지 조건에 따라 DFS를 변형 해주면 된다.
- 루트인 center(minho)는 금액 정산을 하지 않아도 된다.
- 10% 감한 금액에서 원단위는 절사해서 배분한다.
2번 같은 경우는 내게 시간초과를 안겨준 지옥같은 테스트 케이스가 되었다. 0원 인경우에서 계속 탐색을 하게 되어서 무한 루프에 빠져버렸기 때문 그로므로, money가 0원이 될 경우에는 분배할 필요가 없으므로, DFS를 빠져나온다.