[프로그래머스] 거스름돈 (JavaScript)

프로그래머스 거스름돈

문제풀이

JavaScript로 구현하면서 좀 더 효율적인 방법을 생각해봤는데 기존의 2차원 dp 테이블을 유지할 필요가 없다는 생각이 들었다. 2차원 테이블을 채워나가는 방법이 이전 화폐 구성(위쪽 행)을 바탕으로 하는 것이므로 이전 행을 갱신하는 방식이다. 따라서 1차원 dp 테이블을 갱신시켜나가는 방식으로 충분했다. 그런데 동일하게 O(n^2)의 시간복잡도를 가지기 때문에 공간복잡도에서의 이득밖에 없다.

• 배열을 생성할 때 new Array(길이)를 이용할 경우 빈 배열을 생성한다 즉, 길이는 가지지만 undefined로 채워져있다.

구현코드

function solution(n, money) {
    let dp = [1];
    for(let i = 0 ; i < n ; ++i) dp.push(0);
    
    money.map(unit => {
        dp[unit] += 1;
        for(let i = unit + 1 ; i <= n ; ++i){
            dp[i] += dp[i - unit];
        }
    });
        
    return dp[n];
}