내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
프로그래머스
»
매출 하락 최소화
ps:problems:programmers:72416
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 매출 하락 최소화 ====== ===== 풀이 ===== * 트리에서의 DP를 이용하는 문제. * 사실 내가 푼 아래 코드와 [[https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/|공식 풀이]]가 거의 일치한다. 그래서 풀이는 생략. * DP table을 명시적으로 만드는 대신 functools.lru_cache를 붙이는 것으로 처리했다. ===== 코드 ===== <dkpr py> """Solution code for "Programmers 72416. 매출 하락 최소화". - Problem link: https://programmers.co.kr/learn/courses/30/lessons/72416 - Solution link: http://www.teferi.net/ps/problems/programmers/72416 """ import functools def solution(sales, links): @functools.lru_cache(maxsize=None) def min_sales(node, should_include_root): children_sum = sum(min_sales(c, False) for c in children[node]) sales_including_root = sales[node] + children_sum if should_include_root: return sales_including_root sales_without_root = children_sum + min( (min_sales(c, True) - min_sales(c, False) for c in children[node]), default=0) return min(sales_including_root, sales_without_root) children = [[] for _ in sales] for a, b in links: children[a - 1].append(b - 1) return min_sales(0, False) </dkpr> {{tag>프로그래머스 ps:problems:programmers:Level_4}}
ps/problems/programmers/72416.txt
· 마지막으로 수정됨: 2021/01/30 15:49 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로