[프로그래머스] 완전범죄

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

프로그래머스

처음 문제를 보고 단순히 접근했을 때 dfs 방식으로 진행하면 되겠다는 생각이 들었음

 

하지만 제한사항이 작은 수임에도 불구하고 dfs방식을 채택하면 2의 승수로 경우의 수가 늘기 때문에 시간초과가 발생함

 

계속해서 문제를 이해하려 할 때 떠오르는 것은 DP방식이었음 하지만 어떻게 활용할 지에 대해 떠오르지 않았음

 

GPT에 질문 결과 DP의 배열은 B가 남긴 흔적 기준으로 만들고 B가 남긴 흔적 기준 A가 남긴 최소 흔적의 합을 저장해 주면 됨

 

반복문을 통해 m만큼 순회하면서 DP에 담긴 A흔적을 바탕으로 선택에 따른 흔적 최신화 해줌

 

next를 재할당 하는 것에 대해 이해하는데 어려움이 있었지만 DP배열을 통해 계속해서 계산하면 이전 상태들과 현재 상태가 뒤엉키게 되어 문제 풀이를 할 수 없음을 깨달음

 

추가로 현재 DP상태는 info를 순회하는 index까지의 A 또는 B의 선택에 대한 모든 상태를 가지고 있음

 

따라서 DP배열의 최솟값이 A 흔적에 대한 최솟값이 됨

 

DP방식으로 접근할 때 점화식과 전이 방법에 대해 연습이 더 필요함

function solution(info, n, m) {
    var answer = 0;
    
    let dp = Array.from(Array(m), () => Infinity);
    
    dp[0] = 0;
    
    for(let [a, b] of info){
        const next = Array.from(Array(m), () => Infinity);
        
        for(let i = 0; i < m; i++){
            const aTrace = dp[i];
            if(aTrace == Infinity) continue;
            
            if(aTrace + a < n){
                next[i] = Math.min(next[i], aTrace + a);
            }
            
            if(i + b < m){
                next[i + b] = Math.min(next[i + b], aTrace)
            }
        }
        
        dp = next;
    }
    
    answer = Math.min(...dp);
    
    answer = answer == Infinity ? -1 : answer;
    
    return answer;
}