[프로그래머스][브루트 포스] 힌트 스테이지

     

목차

 

문제

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

프로그래머스

 

문제 구현 방향

해당 문제는 2의 16승정도로 완전 탐색만 잘 구현하면 풀 수 있다.

아래와 같이 간략한 흐름이라고 생각하면 쉽게 구현 가능하다.

// 아주 매운맛을 다 뺀 완전 탐색의 뼈대 모양
function 가보자(스테이지번호) {
    if (마지막) return 비용;
    
    let 안사고_쭉_갔을때_비용 = 이번스테이지비용 + 가보자(다음스테이지);
    let 사고_쭉_갔을때_비용 = 이번스테이지비용 + 번들비용 + 가보자(다음스테이지);
    
    return Math.min(안사고_쭉_갔을때_비용, 사고_쭉_갔을때_비용);
}

 

 

코드 구현

function solution(cost, hint) {
    var answer = 0;
    let len = cost.length;
    let rowLen = cost[0].length-1;
    let myHints = new Array(len+1).fill(0);
    
    function dfs(step, myHints){
        if(step === len-1){
            return cost[step][Math.min(myHints[step], rowLen)];
        }
        
        //1. 해당 번들을 사고 갈 경우
        let bundleCost = hint[step][0];
        let bundleHints = hint[step].slice(1);
        
        bundleHints.forEach((item)=>myHints[item-1]++);
        
        let curBuyHint = myHints[step];
        let curBuyStageCost = cost[step][Math.min(curBuyHint, rowLen)];
        
        let bundleOCost = curBuyStageCost + bundleCost + dfs(step+1, myHints);
        
        bundleHints.forEach((item)=>myHints[item-1]--);
        
        let curNoBuyHint = myHints[step];
        let curNoBuyStageCost = cost[step][Math.min(curNoBuyHint, rowLen)];
        
        //2. 해당 번들을 사지 않고 갈 경우
        let bundleXcost = curNoBuyStageCost + dfs(step+1, myHints);
        
        return Math.min(bundleXcost, bundleOCost);
        
    }
    
    answer = dfs(0, myHints);
    
    
    return answer;
}