[프로그래머스 lv3] 다단계 칫솔 판매 풀이

해설

서로의 추천 관계를 그래프(트리)로 만들어놓자.

특정인 x에 대하여 수익 n이 발생했을 때, 부모 노드인 추천인을 따라가면서 재귀적으로 수익을 분배하면 된다.

수익 분배는 n/10만큼씩 부모 노드 방향으로 진행되다가, 더이상 위의 추천인이 없거나 배분할 금액이 없을 때 중단된다.

수익을 재귀적으로 분배한 후, enroll 배열에 있는 이름의 순서대로 수익을 나열하여 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

map<string, int> benefit;
map<string, vector<string>> graph;

void setGraph(const vector<string>& enroll, const vector<string>& referral) {
    
    for (int i=0; i<enroll.size(); i++) {
        if (referral[i] == "-") continue;
        graph[enroll[i]].push_back(referral[i]);
    }
}

void share(string x, int n) {
    
    int minus = n/10;
    int add = n-minus;
    benefit[x] += add;
    
    if (graph[x].size() == 0 || !minus) return;
    share(graph[x][0], minus);
}

vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    
    setGraph(enroll, referral);
    
    for (int i=0; i<seller.size(); i++)
        share(seller[i], amount[i]*100);
    
    vector<int> ans;
    for (auto x : enroll) 
        ans.push_back(benefit[x]);
    return ans;
}