[programmers] 매출 하락 최소화_DP

[2021 KAKAO BLIND RECRUITMENT] 매출 하락 최소화

link

풀이

• 방식 : Tree순회, DP를 통한 Cost 최소값 찾기
• 재귀함수를 사용하여 DP를 Update하는 방식으로 진행(재귀 함수 구성 가장 작은 Block를 어떻게 구성할지 고민하자)
• 전역변수로 Cost 선언(문제에서 주어진 최대 크기 만큼 선언)
• Cost update의 경우 자식 Node 전체를 돌면서 최소 Cost를 더해줌
• 만약 자식 Node 전체가 불참으로 선택될 경우 자식 중 Cost가 제일 작은 값을 더해줌

📰code

dn_links = [[] for _ in range(300000)]
cost = [[0,0] for _ in range(300000)]

def search(sales, node):
    cost[node][0] = 0
    cost[node][1] = sales[node]
    extra=10000+1

    if not dn_links[node]:
        return 
    
    for dn_link in dn_links[node]:
        search(sales, dn_link)
        if cost[dn_link][0] < cost[dn_link][1]:
            cost[node][0] += cost[dn_link][0]
            cost[node][1] += cost[dn_link][0]
            extra=min(extra,cost[dn_link][1]-cost[dn_link][0])
        else : 
            cost[node][0] += cost[dn_link][1]
            cost[node][1] += cost[dn_link][1]
            extra = 0
    cost[node][0] += extra 
        
def solution(sales, links):

    for link in links:
        dn_links[link[0]-1].append(link[1]-1)
    
    search(sales, 0)
    
    return min(cost[0])

💡 수정 필요한 내용은 댓글이나 메일로 알려주시면 감사하겠습니다!💡