(코테) 프로그래머스_거스름돈 *dp

 

문제 링크

 

https://school.programmers.co.kr/learn/courses/30/lessons/12907?language=java

 

 

 

import java.util.*;

class Solution {
    public int solution(int n, int[] money) {
        int answer = 0;
        int[] dp = new int[n+1];
         final int flag = 1_000_000_007;
        
         //Arrays.sort(money);
          dp[0]=1;
        
        for(int coin:money){
            for(int i=coin;i<=n;i++){                
                dp[i] = (dp[i] + dp[i-coin]) % flag;                
            }            
        }                          
        
        return dp[n];
    }
}

 

 

 

회고

거스름돈 - dp 

처음에 접근법을 파악 못하고 다른 사람 풀이를 참조하였다... 근데 왜 이렇게해서 풀리지? 원리가 사실 이해가 안됐음.

 

 

ex) n =5  동전 = [1,2,5]

아래 표를 보면 0 동전을 제외하고 

각 동전별  합을 구하는 케이스이다

            0~8까지

동전 1 -   

동전 2 -

동전 5- 

 

중요한 포인트가 이전 동전에서 구하려는 합 + 내가 새로 추가하는 동전?의 합을 구해주면 된다 
-< 사실 이부분이 처음에 너어어무 이해가 안돼서 좀 이해하는데 오래걸렸다. 

코드로는  dp[i]  = dp[i-1] + dp[i-coin] ; 신규 동전에 대한 합을 추가시키는 공식이다. 

 

 

동전 2의 풀이를 예로 들어보겠다.

동전 2로 0~8을 구하는 방법은 이전에 구해놨던 동전의 케이스들에서 2를 신규로 넣어주면 되는데 

케이스는 2개 케이스가 있다. 

하나는 이전 동전의 목표합의 갯수           -> 이전 동전의 목표합의 모든케이스에  현재 동전을 더해주면 적합!!

두번째는 현재 동전에서 (목표합-현재동전값)의 갯수     ->현재 동전에서    (목표값-현재 동전값) 한거의 모든케이스에  현재 동전값을 더해주면 적합해짐.

 

그래서 위 2케이스의 합을 구해주면 현재 동전의 모든케이스의 누적합이 완성됨!

1. 동전2 케이스에서  목표값 5읜 경우  

  1-1  이전 동전 1의 목표값 5인케이스 -> 1개 경우의수

  1-2  현재 동전(2) 에 (    5(목표값) - 2(현재동전) )  즉 , 2번동전 목표가 3 케이스  -> 총 2개의 경우의수

위 1-1 , 1-2 의 경우의 수 합치기  =  3      

 

위와 같이 누적해서 dp를 채워주면 된다.