[DFS] 다단계 칫솔 판매 - 2021 Dev-Matching

난이도가 Level3인 것 치고는 쉽게 해결한 것 같다. 이 문제는 DFS로 해결할 수 있으며, 분배금을 10% 떼어내고 남은 몫은 자신이 가지고 다음 노드(인원)에게 10%의 분배금을 전달하는 과정을 반복하면 된다.

그리고 일일이 간선을 연결하는 과정 없이 map을 활용하여 간단히 DFS를 수행할 수 있다.

주의할 점이 있다면, 분배금이 1원 미만일 때에도 DFS를 진행하면 시간초과가 난다. 그래서 반드시 분배금이 있을 때만 DFS 함수를 호출해야 한다.

 

 

소스 코드

#include <vector>
#include <map>
using namespace std;

map<string, int> mres;
map<string, string> mref;
vector<int> answer;

void distribute(string seller, int money) {
    if(seller=="-") return; // root(center)에서 끝낸다.
    int part = money*0.1;
    mres[seller]+=money-part;
    if(part) distribute(mref[seller], part); // 분배할 금액이 있는 경우에 추천인에게 10%를 돌린다.
}

vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    //map에 데이터 저장
    for(int i=0;i<enroll.size();i++){
        mres[enroll[i]]=0;
        mref[enroll[i]]=referral[i];
    }
    for(int i=0;i<seller.size();i++) distribute(seller[i], amount[i]*100);
    for(int i=0;i<mres.size();i++) answer.push_back(mres[enroll[i]]);
    return answer;
}

 

테스트케이스 13개 모두 정답