내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
프로그래머스
»
다단계 칫솔 판매
ps:problems:programmers:77486
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 다단계 칫솔 판매 ====== ===== 풀이 ===== * 특별한 알고리즘 없이 그냥 그대로 구현하면 된다.. * 자식이 업데이트될때 부모들도 똑같은 값이 증가된다면, 오일러 트리 테크닉과 세그먼트 트리를 이용하여 효율적으로 푸는 방법을 고민해 볼수 있겠지만, 이 문제는 그렇게 하기도 쉽지 않거니와 그렇게 할 필요도 없다. 이익이 최대 100*100 = 10000원이기 때문에, 10%씩 부모에게 떼어주는 것을 반복하면, 업데이트 되는 노드의 갯수는 최대 5개뿐이다. 따라서 한개의 쿼리에 5개 이하의 노드만 업데이트해주면 되므로 그냥 O(1)으로 생각할수 있다. n개의 노드로 트리를 만드는 데에는 O(n), m개의 쿼리를 각각 O(1)에 처리하는 데에는 O(m). 총 시간복잡도는 O(n+m). ===== 코드 ===== <dkpr py> """Solution code for "Programmers 77486. 다단계 칫솔 판매". - Problem link: https://programmers.co.kr/learn/courses/30/lessons/77486 - Solution link: http://www.teferi.net/ps/problems/programmers/77486 """ import collections COST = 100 def solution(enroll, referral, seller, amount): parents = {child: parent for child, parent in zip(enroll, referral)} parents['-'] = '-' profits = collections.defaultdict(int) for s, a in zip(seller, amount): profit = a * COST member = s while profit > 0: profit_to_referral = profit // 10 profits[member] += profit - profit_to_referral profit, member = profit_to_referral, parents[member] return [profits[x] for x in enroll] </dkpr> {{tag>프로그래머스 ps:problems:programmers:Level_3}}
ps/problems/programmers/77486.txt
· 마지막으로 수정됨: 2021/07/08 16:40 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로