프로그래머스 거스름돈(Java, LV3) /DP

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

코딩테스트 연습 - 거스름돈

 

풀이

DP 문제 중 가장 대표중인 문제, 화폐 거스름돈과 유사한 문제이다.

단, 차이점은 지불할 수 있는 방법의 수를 계산하는 것이다.

 

점화식을 세우고 진행하는데, 2차원 배열을 통해 처음 접근했다.

d[i][j] = i개의 화폐(moeny[0..i])로 j 금액을 낼 수 있는 방법 수

d[i][j] = d[i-1][j] + d[i][j-money[i]] 가 된다

 

이 때, 화폐별로 for문을 돌면서 지불방법을 갱신하며 더한다.

https://gurumee92.tistory.com/64

그런데 위와 같은 방법으로 고려했을 때, 불필요한 연산들이 있다.

바로 아래의 사진을 보자.

 

파란 부분 주목(2행 5열의 1,2 -> 4 는 2가아니라 3...) 

파란색 부분은 결국 값이 동일하기에 갱신할 필요가 없다.

왜냐하면, 새롭게 추가된 화폐 money[i]의 값을 더해서 낼 방법이 없는 경우들이기에 결과적으로 불필요한 연산을 수행하게 되는 것이다.

 

따라서, 효율성을 위해 

d[j] = 금액 j를 낼 수 있는 방법 수

에 대해서, 사용할 화폐 수에 대해 for문을 돌며 체크한다.

d[j] = d[j] + d[j-money[i]] 

단, 처음 화폐 1개를 통해 지불 방법 갱신, for문 도는 조건을 잘 체크해서 문제 접근하기

import java.util.*;

class Solution {
    public static final int INF = -1;
    public int solution(int n, int[] money) {
        int answer = 0;
        Arrays.sort(money);
        
        // variable
        long[] d = new long[n+1];
    
        // 초기화(화폐 한개 지불 방법)
        for(int i =0; i<=n ;i++){
             if(i % money[0] == 0)
                 d[i]=1;
        }
        
        // 화폐단위 개수별로 for문
        for(int i=1; i<money.length ; i++){
            // 화폐 이전까지의 합 + 새로운 화폐로 낼 수 있는 방법
            for(int j=money[i]; j<=n; j++){
                d[j] += d[j-money[i]];
            }
        }
        
        // 형 변환
        answer = (int)(d[n] % 1000000007);
        return answer;
    }
}