프로그래머스 2021 Dev-Matching 77486 - 다단계 칫솔 판매(트리 순회)

프로그래머스 2021 Dev-Matching 77486 - 다단계 칫솔 판매(트리 순회)

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

- 문제가 처음 나온 5달 전에는 못 풀었는데 지금은 너무 쉽게 풀었음

- 전체 트리를 정의하고, 노드 마다 번 돈을 읽어내려가면서 부모까지 순회하면서 fee를 더해준다. 여기서 민호까지 수수료를 전달해줘야 하므로 parent[0]은 -1로 해준 뒤 순회하는 함수의 basis로 사용해준다.

- 이름을 미리 인덱스로 파싱해두는 해쉬를 하나 선언해서 열거형처럼 써서 편하게 풀었다.

#include #include #include using namespace std; unordered_map umap; // 0은 민호 int parent[10001]; int totalEarn[10001]; vector answer; void giveFee(int idx, int money) { if(parent[idx] == -1) { // 민호면 돈 다 먹고 종료 totalEarn[idx] = money; return; } int fee = money / 10; // 19 * 10% = 1 totalEarn[idx] += money - fee; giveFee(parent[idx], fee); } // enroll 1만, seller 10만 vector solution(vector enroll, vector referral, vector seller, vector amount) { int mNum = enroll.size(); int selNum = seller.size(); // 1. 트리 만들고 parent[0] = -1; // 민호는 부모없음 for(int i = 0; i

from http://ellerymoon.tistory.com/52 by ccl(A) rewrite - 2021-08-14 01:00:18