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

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

프로그래머스

문제를 접했을 때 트리가 보여 DFS, BFS로 접근하려 했음, 하지만 최상단부터 처리하는 것은 어려워 보여서 최하단부터 시작하여 거꾸로 계산하면 되는 것을 생각함.

 

다만, 해당 문제에 대한 갈피를 제대로 잡지 못했음. 그래서 GPT에 질문 결과 DFS + DP 문제라는 결론을 얻게 됨.

 

dp의 구성은 해당 인덱스의 노드가 선택되지 않았을 때와 선택됐을 때의 값을 저장함.

 

트리의 가장 끝 노드는 선택됐을 때 본인의 매출액, 그렇지 않으면 0을 가짐.

 

그룹에서 팀장이 선택되었을 때 팀원들의 참석 여부는 선택사항이므로 팀원들의 최솟값을 더해줌.

 

팀장이 선택되지 않았을 때는 두 가지 경우로 나뉨, 이미 기선택된 팀원이 있거나 선택된 팀원이 없는 경우

 

기선택된 팀원이 있는 경우 팀원들의 최솟값을 더한 값을 대입해 주고 선택된 팀원이 없는 경우 전 팀원 중에서 선택됐을 때 매출액에서 선택되지 않을 때 매출액을 뺄셈 하여 최솟값을 팀원들의 최솟값을 더한 값에서 빼줌

• 선택된 팀원이 없는 경우 팀원 중에서 한 명을 선택해야 하기 때문에 선택됐을 때 매출액에서 선택되지 않을 때 매출액을 뺄셈 하여 최솟값을 구함
• dp[child][1] < dp[child][0] 의 경우 최솟값을 구하기 때문에 선택됐을 때 값이 작다면 선택된 팀원이라고 할 수 있음

처음 GPT에 질문했을 때 코드의 경우 childSum이 dp[child][0]로 더하는 것으로 되어 있었는데 문제 파악 후 min(dp[child][0], dp[child][1])로 수정함

 

사실상 결론을 보고 문제를 다시 풀이한 케이스라 완전히 이해했다고 할 순 없지만 프로그래머스에 정리된 문제 풀이를 보고 많은 힌트를 얻어 어느 정도 이해할 수 있었음

 

https://school.programmers.co.kr/questions/34874

프로그래머스

function solution(sales, links) {
    var answer = 0;
    
    const empCnt = sales.length;
    const tree = Array.from(Array(empCnt), () => []);
    const dp = Array.from(Array(empCnt), () => [0, 0]);
    
    links.forEach(link => {
        const [cap, emp] = link;
        tree[cap - 1].push(emp - 1);
    });
    
   const dfs = (node) => {
       if(tree[node].length == 0){
           dp[node][1] = sales[node];
           dp[node][0] = 0;
           return;
       }
       
       dp[node][1] = sales[node];
       let childSum = 0;
       let diff = Infinity;
       let isChildSelect = false;
       
       for(let child of tree[node]){
           dfs(child);
           
           dp[node][1] += Math.min(dp[child][0], dp[child][1]);
           childSum += Math.min(dp[child][0], dp[child][1]);
           
           if(dp[child][1] < dp[child][0]){
               isChildSelect = true;
           }
           
           diff = Math.min(diff, dp[child][1] - dp[child][0]);
       }
       
       dp[node][0] = isChildSelect ? childSum : (childSum + diff);
   }
    
    dfs(0);
    answer = Math.min(...dp[0])
    return answer;
}