사용자 도구

사이트 도구


ps:problems:programmers:72416

매출 하락 최소화

ps
링크https://programmers.co.kr/learn/courses/30/lessons/72416
출처프로그래머스
문제 번호72416
문제명매출 하락 최소화
레벨Level 4
분류

DP

시간복잡도O(n)
인풋사이즈n<=300,000
사용한 언어Python
해결날짜2021/01/29
출처2021 KAKAO BLIND RECRUITMENT

풀이

  • 트리에서의 DP를 이용하는 문제.
  • 사실 내가 푼 아래 코드와 공식 풀이가 거의 일치한다. 그래서 풀이는 생략.
  • DP table을 명시적으로 만드는 대신 functools.lru_cache를 붙이는 것으로 처리했다.

코드

"""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)

토론

하민수, 2021/02/28 08:30
진짜많이 배우고갑니다. 보고 많이 공부하겠습니다.
댓글을 입력하세요:
Q E L M S
 
ps/problems/programmers/72416.txt · 마지막으로 수정됨: 2021/01/30 15:49 저자 teferi