[CodeKata] 프로그래머스(Lv3) : 거스름돈

🥋 Oooth More!! (Level 3) 

 

 

🧮 풀이

나는 DFS로 접근했지만, 효율성 테스트에서 시간초과가 발생했다.

function solution(n, money) {
  let answer = 0;
  money = money.sort((a,b) => b-a);
  
  const DFS = (rest, index) => {
    if (rest === 0) answer++
    return;
    
    const m = money[index];
    const max = Math.floor(rest/m);
    for (let i = max ; i >= 0 ; i--) {
      DFS(rest-m*i, index+1)
    }
  }
  
  DFS(n,0)
  
  return answer
}

DFS() 함수를 만들었고, 인자는 (남은 계산값, money 배열에서의 인덱스) 2가지를 받았다.

m은 현재 인덱스의 화폐값, max는 Math.floor()로 계산한 현재 지폐값을 최대한 많이 사용할 수 있는 개수이다.

현재 화폐값(m)을 max개 ~ 0개까지 사용할 수 있는 경우의 수에 대해 DFS를 돌리며, rest가 0이 되면 answer에 1을 더해준 것이다.

 

이는, index가 (money 인자 개수 + 1)까지 도달해야하기도 하며, rest값이 남아있는 동안은 나머지 money 요소들을 계속해서 대입해보기 때문에 효율성에서 통과를 못한 것 같다.

 

 

🖇 리뷰

모범답안을 보니 생각보다 풀이는 간단했다.

 

하지만 지난 포스팅과 유사하게, DP(Dynamic Programming)를 사용하는 아이디어에 착안하는 것이 우선 난해했을 것이다.

이 DP를 통해, 0원 ~ n원까지 계산할 수 있는 모든 방법의 개수를 dp배열에 누적해나간 것이다.

* DP(Dynamic Programming) 참고링크 : https://velog.io/@chelsea/1-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming-DP  

function solution(n, money) {
    const dp = [1, ...new Array(n).fill(0)];
    
    money.forEach(unit => {
        dp[unit] += 1;
        for(let i = unit + 1 ; i <= n ; i++){
            dp[i] += dp[i - unit];
        }
    });
        
    return dp[n] % 1000000007;
}

* 출처 : https://velog.io/@hyeon930/%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-JavaScript

• dp는 길이 (n+1)의 일차원 배열로, 각 index에는 index(원)을 계산할 수 있는 경우의 수를 누적한다.
• money의 모든 요소를 순회하며, 우선 dp[unit]에 1을 더한다. 해당 화폐값(unit) 한 개만 사용해서 계산이 가능하기 때문이다.
• 다음으로, dp의 (unit+1)원 ~ n원까지 순회한다. 여기에, dp[i]번째에 dp[i-unit]을 더해준다. i원을 dp[i - unit]에서의 경우의 수와 현재 화폐값(unit)을 더하는 것으로 계산할 수 있기 때문이다.
• dp[n]은 n원을 계산할 수 있는 모든 경우의 수가 저장되어있다. 이를 최종값을 반환한다. (1,000,000,007로 나눈 나머지)

 

동적 프로그래밍의 원리 자체는 어렵지 않다. 전과 전전의 연산값을 참고해, 현재의 연산값을 누적해나가는 방법이다. (ex) 피보나치 수열)