[SWEA 1970][D2][JAVA] 쉬운 거스름돈

[문제]

 

https://swexpertacademy.com/main/code/problem/problemSolver.do

SW Expert Academy

 

[풀이방법]

 

동전들의 가치를 정수형 배열에 저장한 후, N(거스름돈 총합) / 각 코인의 가치까지 감소시킵니다. 

감소시킬 때마다 각 종류의 돈이 쓰이는 개수를 구해야 하기 때문에 따로 생성한 정수형 배열의 해당 순서의 코인 개수를 증가합니다. 

(dp = 각 코인이 쓰인 개수를 저장하는 정수형 배열)

 

처음에 거스름돈이 주어진 코인의 가치보다 작을 때만 계산을 해야하기 때문에 코인이 거스름돈보다 클 경우에는 다음 코인으로 넘어가도록했습니다. 

 

int[] coins = {50000, 10000,5000,1000,500,100,50,10};
 
            int[] dp = new int[coins.length];
            
            int change = N;
            for (int i =0; i < coins.length; i++) {
                if (coins[i] > N) {
                    dp[i] = 0;
                    continue; //거스름돈보다 화폐 단위 클 경우 
                }
                
                int n = change / coins[i];
                for (int j = 1; j <= n; j++) {
                    change -= coins[i];
                    dp[i]++;
                }
                
            }
            
            for (int i = 0; i < dp.length; i++) {
                sf.append(dp[i] + " ");
            }