프로그래머스[JS] > 거스름돈

프로그래머스 거스름돈

 

🔥문제링크

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

프로그래머스

 

🔥첫번째 풀이 ( 테스트 케이스 모두 통과 but 시간초과 )

처음에 내가 작성한 코드이다. ( 하단 참조 ) 

이 코드는 테스트 케이스는 모두 통과지만 시간초과 테스트에서 모두 시간초과가 나왔다😭 

다른사람들의 코드를 참고해보니 재귀가 아닌 dp ( dynamic programming : 최적화 ) 문제였던 것 같다.

function solution(n, money) {
    let answer = 0;
    money.sort((a,b)=>a-b)    
    const recursive =(rest,arr)=>{
        if(arr.length===0 || rest <=0){
            return
        }
        let fixed = arr.shift()
        if(fixed>rest){
            return
        }
        let count = 0;
        while(1){ 
            if((rest-fixed*count)>0){
                let newArr = [...arr]
                recursive(rest-fixed*count,newArr)
            }else if((rest-fixed*count)===0){
                ++answer
                return
            }else{
                return
            }    
            ++count
        }
    }
    let sliced = money.slice(1)
    let fixed = money[0]
    recursive(n,money)
    

    return answer%1000000007;
}

 

 

🔥두번째 풀이 ( 다른 사람 풀이 참고)

첫번째 풀이에 비해 newArr = [...arr]와 같이 배열을 복사할 필요도 없고 sort()할 필요도 없고 재귀를 사용할 필요도 없어 계산횟수가 확실히 줄어든다. 

 

dp[n] 은 n을 만들수 있는 총 경우의 수를 의미한다.

아래 코드를 보고 연산과정을 곱씹어 보자! 

function solution(n, moneyList) {

    
    let dp = Array(n+1).fill(0)
    dp[0]=1
    
     for(const money of moneyList){
         for(let i=money; i<n+1; ++i){
             dp[i] = dp[i] + dp[i-money]
         }
         
     }
    
    return dp[n]%1000000007
    
}

 

 

🔥참고

https://velog.io/@pmthk__/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EA%B1%B0%EC%8A%A4%EB%A6%84%EB%8F%88-Lv.3-JS

거스름돈 | Lv.3 | JS