[프로그래머스] 2021 Dev-Matching: 웹 백엔드 개발자(상반기) > 다단계 칫솔

https://programmers.co.kr/learn/courses/30/lessons/77486

코딩테스트 연습 - 다단계 칫솔 판매

...중략

문제가 긴것에 비해 쉽게 풀이가 가능한 문제이다.

단순하게 위에 부모노드가 있으면 10%을 주면 된다. 그리고 그 부모노드로 이동해서 계속 반복하면 된다.

그렇게 하기 위해서는 부모노드와 구한 값을 저장할 수 있는 방법이 있어야 한다!

 

[풀이방법]

1. 현재노드의 부모를 저장한다.

2. seller 들의 판매내역인 amount*100 을 기반으로 비용을 계산하기 시작한다.

- seller 노드에서 시작하여 root 노드까지 가야하기때문에 재귀를 사용했다.

2-1. 현재 노드가 root 일 경우, 종료한다.

2-2. amount의 10%인 deliver를 부모노드에게 전달해야하므로 amount에 deliver을 뺀 값을 현재 노드의 cost에 더한다.

     (a) deliver 이 0 일 경우, 더 이상 부모노드에게 전달할 필요 없으므로 재귀를 중단한다.

     (b) 0 이 아닐 경우, 다음 부모노드에게 10% 상납이 가능하므로, (부모노드, deliver)을 파라미터로 재귀함수를 호출한다.

 

#include <string>
#include <vector>
#include <map>

using namespace std;

map <string, string> parent;
map <string, int> cost;

void update_gain(string member, int sell_cost) {
    if(member == "-") return;
    int delivery = sell_cost * 0.1;
    
    cost[member] += sell_cost - delivery;
    
    if(delivery == 0) return;
    update_gain(parent[member], delivery);   
}

vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    vector<int> answer;
    // 1. 부모 저장
    for(int i=0; i<enroll.size(); i++) {
        parent[enroll[i]] = referral[i];
    }
    // 2. 값 계산
    for(int i=0; i<seller.size(); i++)
        update_gain(seller[i], amount[i]*100);
    
    // 3. 결과 리턴
    for(int i=0; i<enroll.size(); i++) {
        answer.push_back(cost[enroll[i]]);
    }

    return answer;
}