[프로그래머스] Lv3. 거스름돈- JavaScript

문제분류 : 코팅테스트 연습

난이도 : Level 3

출처 : 프로그래머스 - 거스름돈

문제

제한사항

📌 내가 생각한 풀이

겹치는 경우의 수를 생각해서, 금액을 기준으로 하는 것이 아닌, 돈의 가짓수를 기준으로 DP를 이용해 풀자.
문제와 같이 주어진 돈이 1,2,5원이고, 만들 금액이 5원이라고 하였을 때
처럼 가능한 경우의 수가 존재한다. 여기서 생각해보면, 2원으로 총액 5원을 만든다고 하였을떄, 3(5-2)원을 만드는 경우의 수가 들어간다. 따라서 겹치는 경우의 수를 포함하여 세어주면 문제가 해결된다.

function solution(n, money) {
    var answer = 0;
    let arr = new Array(n+1).fill(0);
    money.sort((a,b)=>a-b);
    arr[0] = 1;
    money.forEach((d,i)=>{
        for(var i = d; i<=n; i++){
            arr[i] = arr[i-d] + arr[i];
        }
    })
    return arr[n]
    
}

📌 느낀점

기존 DP문제에서 생각하기 어려운 문제였다. 돈의 금액이 기준이 아닌, 가짓수를 기준으로 세우고, 1차원 배열로 공간복잡도를 줄이는 것이 매우 신기하였다.