이 문제의 출처는 프로그래머스입니다.

inn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다.

예를 들어서 손님께 5원을 거슬러 줘야 하고 1원, 2원, 5원이 있다면 다음과 같이 4가지 방법으로 5원을 거슬러 줄 수 있습니다.

  • 1원을 5개 사용해서 거슬러 준다.
  • 1원을 3개 사용하고, 2원을 1개 사용해서 거슬러 준다.
  • 1원을 1개 사용하고, 2원을 2개 사용해서 거슬러 준다.
  • 5원을 1개 사용해서 거슬러 준다.

거슬러 줘야 하는 금액 n과 Finn이 현재 보유하고 있는 돈의 종류 money가 매개변수로 주어질 때, Finn이 n 원을 거슬러 줄 방법의 수를 return 하도록 solution 함수를 완성해 주세요.

제한 사항
  • n은 100,000 이하의 자연수입니다.
  • 화폐 단위는 100종류 이하입니다.
  • 모든 화폐는 무한하게 있다고 가정합니다.
  • 정답이 커질 수 있으니, 1,000,000,007로 나눈 나머지를 return 해주세요.

풀이

  • 중복 조합으로 뽑으면서 해당 값보다 커지면 멈추고 같으면 카운트를 세면 될 것

결과

  • 기본 테스트케이스는 통과를 했지만 효율성 테스트를 시간 초과

수정

2차원 배열을 활용한 DP

  • 1원으로 만들 수 있는 경우의 수 계산

      0 1 2 3 4 5
    1 1 1 1 1 1 1
    2            
    5            

  • 1,2원으로 만들 수 있는 경우의 수

      0 1 2 3 4 5
    1 1 1 1 1 1 1
    2 1 1 2 2 3 3
    5            

  • 1,2,5원으로 만들 수 있는 경우의 수

      0 1 2 3 4 5
    1 1 1 1 1 1 1
    2 1 1 2 2 3 3
    5 1 1 2 2 3 4

  • 점화식

    DP[i][j] = DP[i-1][j - 화폐*(화폐 갯수)]

    const makeArray = (h,w) => Array(h).fill(null).map(_ => Array(w).fill(0));
  
function solution(n, money) {
     
    money.sort((a,b) => a-b);
      
    const len = money.length;    
      
    let DP = makeArray(len,n+1);
      
    for(let i = 0; i <= n; i++){
        DP[0][i] = i%money[0] ? 0 : 1; 
    }
      
    for(let i =1; i < len; i++){
         for(let j = 0; j <= n; j++){
             for(let k = 0; k <= Math.floor(j/money[i]); k++){
                 DP[i][j] += DP[i-1][j-money[i]*k];
             }
         }
    }
    return DP[len-1][n];
}

    위 방식으로 하면 효율성 검사에서 역시 통과를 하지 못합니다.

####O(n^3)에서 O(n^2)으로 줄이기

위 방식으로 작성하게 될 경우 최악의 경우 시간복잡도가 O(n^3)이 나오게 됩니다. 그래서 3번째 for문을 일일히 도는 것이 아니라 규칙을 찾아보면

2원짜리로 4원을 만들 수 있는 경우의 수 = 1원짜리로 4원을 만들 수 있는 경우의 수 + 2원짜리로 2원을 만들 수 있는 경우의 수

즉, 아래와 같은 점화식이 나오게 됩니다.

DP[i][j] = DP[i-1][j] + DP[i][j - money[i]];

계속 DP[i-1][j]에 DP[i][j - money[i]]를 누적시켜 나가기 때문에 2차원 배열이 아닌 1차원 배열로 계속 값을 누적해나가도 상관이 없습니다.

function solution(n, money) {
   
    money.sort((a,b) => a-b);
    
    const len = money.length;    
    
    let DP = Array(n+1);
    
    for(let i = 0; i <= n; i++){
        DP[i] = i%money[0] ? 0 : 1; 
    }
    
    for(let i =1; i < len; i++){
         for(let j = money[i]; j <= n; j++){
             DP[j] += DP[j - money[i]];
         }
    }
    return DP[n];
}

  • 1원 사용

    0 1 2 3 4 5
    1 1 1 1 1 1

  • 2원 사용

    0 1 2 3 4 5
    1 1 1+1 1+1 1+2 1+2

  • 5원 사용

    0 1 2 3 4 5
    1 1 1+1 1+1 1+2 1+2+1

위 방식 처럼 해당 2원을 사용해서 4원을 만들 때는 현재까지 4원을 만드는 방법의 갯수에 2원을 만드는 방법을 더해주면 됩니다.