[ 프로그래머스 ] 다단계 칫솔 판매 (C++) - 구현

---

🔗 문제 링크

프로그래머스

---

💡 문제 풀이 및 해석

 1. 10000명정도의 사람이 들어올 수 있는데, 각각의 사람이 판매 금액의 10%씩 추천인에게 주어야한다.
 2. 여기서 12원일때 1.2원이 되는게 아니고 1원씩 올라가는 것을 보니 int / 10 형식으로 올리는 것 같다.
 3. 단, A->B 에서 12원을 주고, C->B 에서 18원을 줄 때, 따로따로 주면 B->D  에서 각각 1원씩 주지만, 이 계산을 한번에 진행한다면 ( 12+18 ) / 10 = 3 이 되므로 각각 계산해야 한다.

4. 0원일 때, 추천인이 없을 때, 더이상 돈을 위로 안보내도 된다. 

---

⭐️ 정답 코드 및 설명

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

map<string, int> Ref;
int Amount[10001];
int parent[10001];

void Cul(int num, int Cash) {

    int Up = Cash / 10; // 위로 보내줄 금액
    Amount[num] += (Cash - Up); // 이건 내가 먹음
    if (Up == 0 || parent[num] == num) return; // 추천인에게 줄 돈이 없거나, 추천인이 없다면

    Cul(parent[num], Up); // 추천인에게 돈을 보냄

}

vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {

    vector<int> answer;

    for (int i = 0; i < enroll.size(); i++) {
        Ref.insert({ enroll[i],i }); // 이름마다 번호 매칭
        parent[i] = i; // 자기 자신은 추천인이 없음
    }

    for (int i = 0; i < referral.size(); i++) {
        if (referral[i] == "-") continue;
        parent[i] = Ref[referral[i]];
    }

    for (int i = 0; i < seller.size(); i++) {
        int num = Ref[seller[i]]; // 판 사람의 번호
        int Cash = amount[i] * 100; // 판 사람의 금액
        Cul(num, Cash);
    }

    for (int i = 0; i < enroll.size(); i++) {
        answer.push_back(Amount[i]);
    }

    return answer;
}

// 이 아래 코드는 프로그래머스에 제출하기 전에 비쥬얼 스튜디오에서 확인해보기 위해 작성한 것입니다.
int main() {

    vector<string> enroll = {"john", "mary", "edward", "sam", "emily", "jaimie", "tod", "young"};
    vector<string> referral = { "-", "-", "mary", "edward", "mary", "mary", "jaimie", "edward" };
    vector<string> seller = { "young", "john", "tod", "emily", "mary" };
    vector<int> amount = { 12,4,2,5,10 };

    vector<int> answer = solution(enroll, referral, seller, amount);
    for (auto x : answer)
        cout << x << endl;
    return 0;
}

---

🤔 문제 후기

딱히 어려운점이 없었다. Lv.3 문제 치고 상당히 쉬운편이라고 생각한다. 다만, map으로 사람의 이름을 index에 매칭해주는 문제를 풀어보지 않았으면 그 점이 헷갈릴 수는 있겠다고 생각했다.