[LeetCode- Ch8. 동적계획법] 3. 동전 교환 #

https://leetcode.com/problems/coin-change/submissions/

Coin Change - LeetCode

 

참고자료 - 냅색 알고리즘

https://and-some.tistory.com/662

[Ch.10 - DP] 05. 동전교환 [+냅색 알고리즘]

 

 

---

위의 예제와의 차이점

: 예외처리가 필요한데, 존재하지 않는 경우가 있다

-> Integer.MAX_VALUE로 초기화하는 것이 아니라, 총금액의+1로 초기화하는 방법 사용

 

class Solution {
    public int coinChange(int[] coins, int amount) {
        //동전 교환
        //DFS 방식과 DP 방식의 문제 풀이 존재
        //: n이 매우 커지면 DFS 방식은 타임리밋 발생
        
        int[] dp = new int[amount+1];
        
        //초기화를 amount+1로 하는 이유 : 예외처리를 하기 위해서
        //-> 거스름돈의 개수가 총 금액보다 클 수 없기 때문에, 총금액보다 +1 큰수를 넣고,
        //마지막까지 그 수가 존재한다면, 예외처리를 수행한다.
        Arrays.fill(dp, amount+1);
        
        //0번방이 필요한 이유
        //-> 동전 종류와 같은 거스름돈의 경우 dp[0]을 기준으로 +1하기 위해서
        dp[0]=0;
        
        //1,2,5
        //11
        //1 삽입 더 작으면
        //2 삽입 더 작으면
        //5 삽입 더 작으면
        
        //0, 1, 2, 3, 4, 5
        //0, 1, 1, 2, 2, 1 ...
        //dp는 해당 값이 필요한 동전의 최소 개수
        
        for(int i=0;i<coins.length;i++){
            for(int j=coins[i];j<=amount;j++){
                
                //dp[j-coins[i]] = 현재 위치에서 해당 동전크기의 뺀 위치에서의 최소동전필요개수
                //1원 2원 5원
                //i) 1원일때 1원부터 총액수까지 돈다.
                //1원일 경우 -> dp[1-1]+1보다 dp[1]가 크면 -> dp[0]+1 = 1
                //2원일 경우 -> dp[2-1]+1보다 dp[2]가 크면 -> dp[1]+1 = 2
                //3원일 경우 -> dp[3-1]+1보다 dp[3]가 크면 -> dp[2]+1 = 3
                //4원일 경우 -> dp[4-1]+1보다 dp[4]가 크면 -> dp[3]+1 = 4
                //5원일 경우 -> dp[5-1]+1보다 dp[5]가 크면 -> dp[4]+1 = 5
                //....
                //동전 종류 1원일 경우 : dp[j]= {0,1,2,3,4,5,6,7,8,9,10,11};
                
                //ii) 2원일 때 2원부터 총액수까지 돈다.
                //2원일 경우 -> dp[2-2]+1보다 dp[2]가 크면 -> dp[0]+1 = 1
                //3원일 경우 -> dp[3-2]+1보다 dp[3]가 크면 -> dp[1]+1 = 2
                //4원일 경우 -> dp[4-2]+1보다 dp[4]가 크다 -> dp[2]+1 = 3
                //5원일 경우 -> dp[5-2]+1보다 dp[5]가 크면 -> dp[3]+1 = 3
                //....
                //동전 종류 2원일 경우 : dp[j]= {0,1,2,3,3 ....};
                
                dp[j]=Math.min(dp[j], dp[j-coins[i]]+1);
            }
        }
        
   
        //거스름돈의 개수가 초기화한 총 금액+1값 그대로면 -1 반환
        if(dp[amount]!=amount+1) return dp[amount];
        return -1;
    }
}