728x90
🔗 문제 링크
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
💡 문제 풀이 및 해석
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에 매칭해주는 문제를 풀어보지 않았으면 그 점이 헷갈릴 수는 있겠다고 생각했다.
728x90
'문제풀이 > 알고리즘 문제 풀이' 카테고리의 다른 글
[ 백준 14503 ] 로봇 청소기 (C++) - 구현 (0) | 2024.03.06 |
---|---|
[ 백준 1405 ] 미친 로봇 (C++) - DFS (0) | 2024.03.05 |
[ 백준 1379 ] 강의실 2 (C++) - priority_queue (0) | 2024.03.05 |
[ 백준 1027 ] 고층 건물 (C++) - BruteForce (3) | 2024.03.05 |
[ 백준 1344 ] 축구 ( C++ ) - DP (0) | 2024.03.05 |