[프로그래머스][KAKAO_BLIND][2021] 매출 하락 최소화

프로그래머스 코딩테스트 고득점 Kit의 문제입니다.

https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

코딩테스트 연습

 

문제

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

코딩테스트 연습 - 매출 하락 최소화

 

내가 작성한 코드

from collections import defaultdict
import sys

def crew_and_leader(team, leader):
    crews = [] if leader != 1 else [1]
    leaders = []
    for crew in team[leader]:
        if crew in team:
            leaders.append(crew)
        else:
            crews.append(crew)
    return crews, leaders

def get_min_sales(sales, team, team_selected, leader, dp):
    crews, leaders = crew_and_leader(team, leader)
    num_crews, num_leaders = len(crews), len(leaders)

    select = []
    not_select = []

    for l in leaders:
        if dp[leader][l][True] == -1:
            dp[leader][l][True] = sales[l] + get_min_sales(sales, team, True, l, dp)
        select.append(dp[leader][l][True])
        if dp[leader][l][False] == -1:
            dp[leader][l][False] = get_min_sales(sales, team, False, l, dp)
        not_select.append(dp[leader][l][False])
    # crew
    if team_selected:
        min_crew = 0
    else:
        min_crew = min([sales[i] for i in crews]) if num_crews != 0 else sys.maxsize
    choose_crew = min_crew + sum(not_select)
    # leader
    num_not_selected = sum([1 for i in range(num_leaders) if not_select[i] < select[i]])
    if num_leaders == 0:
        choose_leader = sys.maxsize
    elif num_not_selected == num_leaders:
        nw_min_val = sys.maxsize
        for sel in range(num_leaders):
            crnt = select[sel]
            for non in range(num_leaders):
                crnt += not_select[non] if non != sel else 0
            nw_min_val = min(nw_min_val, crnt)
        choose_leader = nw_min_val
    else:
        choose_leader = sum([min(select[i], not_select[i]) for i in range(num_leaders)])

    return min(choose_crew, choose_leader)

def solution(sales, links):
    sales = [-1] + sales
    team = defaultdict(list)
    dp = defaultdict(defaultdict)
    for leader, crew in links:
        team[leader].append(crew)
        dp[leader][crew] = defaultdict()
        dp[leader][crew][True] = -1
        dp[leader][crew][False] = -1

    return get_min_sales(sales, team, False, 1, dp)

• 나눠 생각해야할 문제
  
  • leader가 참가된 상태인지 / 참가되지 않은 상태인지
  • 우리 팀 소속이 팀원인지 / 팀장인지
• 트리
  • 루트가 주어짐
  • 루트부터 단방향으로 탐색 가능
• DP
  • 선택에 따라 서브트리의 최소매출을 중복 계산
  • leader / 팀원 / 선택에 따른 memoization

 

다른 사람이 작성한 코드

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

• 경이롭다
  
  • 내가 하고싶은 로직과 이 분의 로직이 똑같다고 생각한다
  • 그런데 다른 사람의 코드임에도 내가 작성한 코드보다 더 빨리 이해된다
  • 여러 다른 사람들의 코드를 살펴보면서, 이 문제는 짧은 코드로 만들 수 없구나 생각

http://www.teferi.net/ps/problems/programmers/72416

매출 하락 최소화 [테페리넷]

 

기억해야할 것

• @functools.lru_cache(maxzie=None)
  
  • 함수에 대한 파라미터와 결과를 캐싱하여 DP를 간편하게 구현할 수 있다
• min(list, default=0)
  • list가 비었을 때 min 사용이 안됐는데 default를 옵션으로 줄 수 있었다